SRM 565 Div2 （練習） - tshitaの備忘録Ⅱ

結果

oox （練習）
Editorial: http://apps.topcoder.com/wiki/display/tc/SRM+565

Hard問題で解いている途中で問題の解釈を変えていき（簡単な方へ）何故解けないんだという未知との遭遇に出くわしたので反省．HardはEditorialを見ました．

[Easy: ValueHistogram ]

問題

0から9の整数を含む配列valuesが与えられる．ヒストグラムを作る（具体例を見たら一発）．
values = {2, 3, 5, 5, 5, 2, 0, 8} の場合は，

..........
.....X....
..X..X....
X.XX.X..X.

を返す．高さは最も多い出現する整数の頻度+1である．

解法

こういう問題は冗長に思えても愚直にやるというのが良いと思います．

ソースコード

class ValueHistogram {
public:
    vector <string> build(vector <int> values) {
        int n = values.size(), H = 0;
        map<int, int> memo;

        for (int i = 0; i < n; ++i)
            ++memo[values[i]];
        for (auto e : memo)
            H = max(H, e.second);
        ++H;

        vector<string> res(H, "..........");
        for (int i = 1; i < H; ++i) {
            for (int j = 0; j < 10; ++j) {
                if (memo[j] >= H - i)
                    res[i][j] = 'X';
            }
        }

        return res;
    }
};

[Medium: MonstersValley2 ]

問題

モンスターに順番に会っていく．i番目のモンスターに会った時に次の2つの選択が出来る．

price[i]の金額がする賄賂を渡して仲間にする．そして，現在持っている値にdread[i]足される．
現在持っている値がdread[i]以上なら通り過ぎる．しかし，dread[i]よりも小さいなら賄賂を渡す選択しか出来ない．

初めに持っている値は0である．
すべてのモンスターを通り過ぎるのに必要な最小の賄賂の金額を求めよ．

$1 \le dread.size(), price.size() \le 20, 1 \le dread_i \le 2 \times 10^9, price_i \in \{1, 2\}$

解法

モンスターが高々20匹なので，それぞれのモンスターに賄賂を渡すか渡さないかの全探索を行います（場合の数は $2^{20} = 1048576$ 通り）．全列挙を実装ではビット演算で行っています（あり本 pp.143-145 を参考）．ただし，今回のような問題だとEditorialに書かれている方法（バックトラッキング）の方が探索空間が小さくなりそうです．
計算量はモンスターの数をNとした場合 $O(N 2^N)$ です．Div1の問題では $1 \le N \le 50$ となって今回のような全列挙では間に合わないです．Div1に上がった時に練習で解くのでここではスルーします．

ソースコード

class MonstersValley2 {
public:
    int minimumPrice(vector <int> dread, vector <int> price) {
        const int n = dread.size();
        int res = 2 * 30;

        for (int s = 0; s < 1 << n; ++s) {
            ll sum = 0;
            int spent = 0;
            bool flag = true;

            for (int i = 0; i < n; ++i) {
                if (s >> i & 1) {
                    sum += dread[i];
                    spent += price[i];
                }
                else if (sum < dread[i]) {
                    flag = false;
                    break;
                }
            }

            if (flag)
                res = min(res, spent);
        }

        return res;
    }
};