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"; } };