SRM 549 div1 med: MagicalHats

問題

魔法使いとあなたがゲームで勝負をする。

ゲームでは, 二次元座標上にいくつかの帽子を置き, そのいくつかの帽子の中にはコインを隠しておく。
あなたは, numGuess 回だけ, 好きな帽子の中身を見ることができる。ただし, 相手は魔法使いなので, 最初は帽子の中身にコインがあったのに, 帽子の中身を適当に入れ替えることができる。ただし, 矛盾がないように,

一度帽子の中身を見てそこにコインが入っていた場合, そのコインを動かすことはできない。
一度帽子の中身を見てそこにコインが入っていなかった場合, その帽子にコインを入れることはできない。

という制約はあるものとする。

また,

各行について, 帽子の数 + コインの数は偶数
各列について, 帽子の数 + コインの数は偶数

というのも成り立っていなければならない。

帽子のおいてある座標, コインそれぞれの価値が与えられる。あなたの目的は帽子の中身を見たコインの価値の合計を最大化することで, 魔法使いの目的はそれを最小化することである。双方が最適に動いた場合, あなたが得られるコインの価値の合計はいくらか。

解法

まず問題を単純化します。魔法使いのほうは, コインを好きに動かすことができるので, 同じ枚数コインを見られるなら, 価値の少ないものから順にコインを見られるのが良いはずです。ということで, この問題の争点は, 「何枚のコインを見られるか？」ということになります。

そこで, 各帽子の状態を, 「まだ見てない」「見てコインがないことがわかった」「見てコインがあることがわかった」の 3 つに分けます。これで dp[state] = (state の状態から得られるコインの最大枚数)という dp をすればよさげな気がします。

state が分かれば, 同時に「何枚のコインを取ったか」, 「何個の帽子を見たか」, 「各行の偶奇」のようなものもわかるので, 状態としては state で十分です。遷移もそんなに難しくないと思います。

個人的に難しかったのは, 「valid であることの判定」です。numGuesses 個の帽子を開いた後も, 帽子を開く作業を続けていけば, 今の帽子の状態が valid であるかどうかがわかります。これは dfs をそのまま続けているだけなので, 計算量は O(n*3^n) のままです。

const int INF = 1e9;
int dp[2000000], p3[15];
vector<string> board;
vector<int> coins;
vector<pii> pnts;
int numGuesses;

int at(int state, int index) {
    return (state/p3[index])%3;
}

int nextState(int state, int index, int flag) {
    return state + p3[index]*flag;
}

// 0: not revealed
// 1: noCoin
// 2: coin
int dfs(int state, int depth, vi& row, vi& col) {
    int& ret = dp[state];
    if (ret >= 0) return ret;
    int num = pnts.size();
    int coinNum = 0;
    for (int i = 0; i < num; i++) {
        if (at(state, i) == 2) coinNum++;
    }
    if (depth == num) {
        if (coinNum != coins.size()) return ret = INF;
        // valid なら 0, そうでないなら INF
        for (int el : row) 
            if (el%2) return ret = INF;
        for (int el : col) 
            if (el%2) return ret = INF;
        return ret = 0;
    }
    ret = 0;
    for (int i = 0; i < num; i++) if (at(state, i) == 0) {
        int tmp = INF;
        // コインをばらす
        if (coinNum < coins.size()) {
            int nstate = nextState(state, i, 2);
            int plus = (depth < numGuesses);
            tmp = min(tmp, plus+dfs(nstate, depth+1, row, col));
        }
        int nstate = nextState(state, i, 1);
        row[pnts[i].first] += 1;
        col[pnts[i].second] += 1;
        tmp = min(tmp, dfs(nstate, depth+1, row, col));
        row[pnts[i].first] -= 1;
        col[pnts[i].second] -= 1;
        ret = max(ret, tmp);
    }
    return ret;
}

class MagicalHats {
public:
    int findMaximumReward(vector <string> _board, vector <int> _coins, int _numGuesses) {
        board = _board;
        coins = _coins;
        numGuesses = _numGuesses;
        pnts.clear();
        int R = board.size(), C = board[0].size();
        for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
            if (board[i][j] == 'H') pnts.emplace_back(i, j);
        }
        memset(dp, -1, sizeof(dp));
        p3[0] = 1;
        for (int i = 1; i < 15; i++)
            p3[i] = p3[i-1]*3;
        vi row(R), col(C);
        int num = dfs(0, 0, row, col);
        if (num >= INF) return -1;
        sort(coins.begin(), coins.end());
        int ret = 0;
        for (int i = 0; i < num; i++) {
            ret += coins[i];
        }
        return ret;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 549 div1 med: MagicalHats

問題

解法