SRM 511 div1 med:FiveHundredEleven

なるほどという感じのdpだった。難しいdpに全く気づかない。

問題

Fox CielとToastmanがゲームをする。
n枚のカードおよび0に初期化された数nowを準備する。各プレイヤーは順番にカードを1枚ずつ取り除いていく。取り除く際,そのカードに書かれた数字をnowにor演算する。
nowを511にしてしまうか,取るカードがなくなると負けである。各々が最善を尽くした場合どっちが勝つでしょう。

解法

普通にdpしようとするとdp[now][state] = 今数がnowになっていて残っているカードがstateで表されるときに勝つか負けるか
というような感じでdpをすることになりますが,これは状態が多すぎて死にます。

しかし,よく考えると,stateとしては「残ったカードが何枚か」ということだけ覚えておけば十分であることに気づきます。
例えば,now = 7という状況を考えてみましょう。この場合,カードとして16というカードがあったとしても16をとっていることはありえないです。なぜなら,orを取り続ける演算をする場合,一度16を取ってしまったらnowは16以上になるはずなのでnow=7という状況はありえません。

そんな感じで,実はnowが決まっていると,stateもある程度制限されてしまい,実はのこったカードの状態だけを考えれば完全に遷移が決定してしまいます。

具体的に遷移を考えてみます。

各状態において,nowという数をor演算子を使うと変化させることのできるカードの枚数(changeとする)を数えます。

残っているカードには下図のような包含関係があるので,change < rest であればnowを変化させないカードを取ることも許されます。

そんな感じでカードを取った時,相手が必敗になるなら勝ちです。どんなカードをとっても相手が勝つなら負けです。

int dp[512][55];
vector<int> card;

int dfs(int now, int rest) {
    if (now == 511) return 1;
    if (rest == 0) return 0;
    int& ret = dp[now][rest];
    if (ret != -1) return ret;
    int change = 0;
    for (int el : card) {
        if ((now|el) != now) change++;
    }
    for (int i = 0; i < (int)card.size(); i++) {
        if ((now|card[i]) != now) {
            if (!dfs(now|card[i], rest-1)) return ret = 1;
        } else {
            if (change < rest) {
                if (!dfs(now, rest-1)) return ret = 1;
            }
        }
    }
    return ret = 0;
}

class FiveHundredEleven {
public:
    string theWinner(vector <int> cards) {
        card = cards;
        memset(dp, -1, sizeof(dp));
        if (dfs(0, card.size())) return "Fox Ciel";
        else return "Toastman";
    }
};