AOJ 1518 - Last One
Last One | Aizu Online Judge
提出コード
グランディ数についての問題を初めて解きました。
数週間前にこちらのブログを読んでいたので、知識としてはなんとなくありました。
この記事に書いてあることさえわかれば、この問題はなんとなくで解けてしまいます。
step1が終わった時点で空集合になったら負けなので、勝ちたいのであれば、相手のstep2が終わった時点での全ての数字についてxorをとったものが0になるように、こちら側の手番で処理を行っていけばいいです。
- step2終了時点での集合S内の全ての数字のxorが0であれば、次のstep2ではxorは絶対0になることはありません。
また、
- step2終了時点での集合S内の全ての数字のxorが0でなかったら、次のstep2でxorを0にする方法が必ず存在します。
この2つの条件がそろったので、グランディ数についての理論を使えば答えが求まります。
ということで、お互いが最善を尽くした時、最初のstep2での集合Sについて、全ての数字のxorをとったときが0であれば負け、0でなければ勝ちという風に初めから勝敗が決まっています。
あとは、入力をすべて2進数に直す操作と、xorをとっていく操作をして、0であるかどうか調べればこの問題が解けます。
