読者です 読者をやめる 読者になる 読者になる

SRM608 Div2 (復習)

参加出来なかったので復習.

反省点

  • 説明が上手くできない.
  • 問題文の理解に時間がかかる・(向いていないかも・・・)

[250 OneDimensionalRobotEasy]

通した.

(問題文)

1次元の数直線上で[-A, B]の範囲をロボットが動く.初期位置は原点0.
コマンドが文字列で与えられる.
i番目の文字はi番目の命令で,'R'ならば右に,'L'ならば左にロボットが移動する.
ただし,-Aの場所で'L'が与えられても-Aにとどまる.
また,Bの場所で'R'が与えれてもBにとどまるとする.
この時,すべての命令によって動いたロボットの最終位置を答える.

(方針)

シミュレーションなので問題分の通りに実装.

[500 MysticAndCandiesEasy]

通した.
問題文を理解するのに時間がかかった.
なんとなくで通してツライ.

(問題文)

N個の中身が見えない箱が与えられていて,C個のキャンディがいづれかの箱に入っている.
i番目の箱には0からhigh[i]個のキャンディが入っている.
最低何個の箱を開ければX個以上のキャンディが得られるかを答える.

(方針)

一般的な説明が上手く出来ないので次の例で示す.
C = 100, X = 63, high = {12, 34, 23, 45, 34}.

highが小さい順にソートする.
higi = {12, 23, 34, 34, 45}

1. ここで,highが12の箱に12個のキャンディが入っていたとしたら,
残りの箱には最低でも100 - 12 = 88個キャンディが入っている.
2. 次に,highが23の箱に23個のキャンディが入っていたとしたら,
残りの箱には最低でも88 - 23 = 65個のキャンディが入っている.
3. 次に,highが34の箱に34個のキャンディが入っていたとしたら,
残りの箱には最低でも65 - 34 = 31個のキャンディが入っていることになる.

欲しいキャンディの個数は最低63(= X)個であるから,3のhighが34の箱は開ける.
よって,開けるのは{34, 34, 45}の3個の箱である.

[1000 BigOEasy]

解けなかった.
トポロジカルソートと思ったら違うみたい.
問題文を理解してEditorialを読んで後でまとめる(詳しくは
Login - TopCoder Wiki)

(問題文)

有向グラフが隣接行列が与えられる.
大きなLに対して,長さLの歩道の数が多項式関数で抑えられるかを判別する問題.

(方針)

ソースコード

[250 OneDimensionalRobotEasy]

#include <iostream>
#include <vector>

using namespace std;

class OneDimensionalRobotEasy {
public:
    int finalPosition(string commands, int A, int B) {
        const int n = commands.size();
		int pos = 0;

        for (int i = 0; i < n; ++i) {
            if (commands[i] == 'R') {
                if (pos + 1 <= B)
                    pos++;
            }
            else { // 'L'
                if (pos - 1 >= -A)
                    pos--;
            }
        }

        return pos;
    }
};

[500 MysticAndCandiesEasy]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class MysticAndCandiesEasy {
public:
    int minBoxes(int C, int X, vector <int> high) {
        const int n = high.size();
	sort(high.begin(), high.end());

        int res = n, sum = 0;
        for (int i = 0 ; i < n; ++i) {
            sum += high[i];
            if (C - sum < X) {
                res = n - i;
                break;
            }
        }

        return res;
    }
};

[1000 BigOEasy]