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}の３個の箱である．

[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]