$ $
$A_1,A_2,\dots,A_N$の数列があり、2人のプレーヤーが一つずつ取っていく。
残った数のXORが0なら勝ち。先手必勝か先手必敗か。
エスパーかなと思いつつなんとかDPしたが当然TLE
典型90問の頃から忘却していなければ、ACできてたかも。
やったこと
XORが0になる数の組み合わせを色々つくった。以下２進数表記。
「011, 101, 110」… 3つのXORが0
「001, 010, 100, 111」… 4つのXORが0
「000011,000101,000110,011110,101110,110110」… 初めの3つのXORが0だが、後の4つでも0。7つ全部でも0。
あわせて0になる数の組み合わせが閉路になるようにグラフを作って、強連結成分分解？
奇数の成分となる閉路の数を数える？
$ $ということで、残りの数のXORを状態にして0になるループの組み合わせを数えてたら時間切れになった。アリバイに提出したコードはTLE。
$A_i$の上限は$2^{30}$程度なので、たとえば$A_i = 2^{i-1} (i=1,2,\dots,30)$ だと30要素しかないのにとりうる状態の数は$2^{30}$。間に合うわけがない理由はコンテスト後に明らかになった。
基本に帰る
XORに拘るのはほどほどにして、ゲーム問題として基本的な考察をすべきであった。
ゲーム問題の基本とは、
- 先手が勝ちの状態に１手で遷移できるのであれば先手必勝
- 先手から遷移できる状態が全て後手にとって必勝なら先手必敗(後手必勝)
そして、考察の基本
- 極端な場合から考える
N=1
$ $極端な場合。カードが1枚しかないとき。
$A_1≠0$なので負けの状態ではない。
先手がその1枚を取って、残り0枚のXORは0なので先手必勝。
N=2
$A_1 ≠ A_2$なので$A_1;xor;A_2≠0$であり負けの状態ではない。
先手が2枚のうちどちらを取ってもN=1の場合に帰着する。
N=1が先手必勝なのでN=2は先手必敗。
N=3
$ $制約より$A_1;xor;A_2;xor;A_3≠0$であり負けの状態ではない。
先手が3枚のうちどれを取っても、残った数を$A_i,A_j;(i≠j)$とすると$A_i ≠ A_j$なので$A_i;xor;A_j≠0$。よってN=2の場合に帰着する。
N=2が先手必敗なのでN=3は先手必勝。
N=4
$ $制約より$ XOR_{i=1}^4 A_i≠0$であり負けの状態ではない。
先手が4枚のうちどれを取っても、残った数を$A_i,A_j,A_k$とすると$A_i;xor;A_j;xor;A_k≠0$。よってN=3の場合に帰着する。よって先手必敗
かというとそうではない。
先ほど挙げた「011, 101, 110」が残る場合など、XORが0になる場合が存在する。
1枚とった後のxorを0にすることができれば先手必勝。
できなければN=3の場合に帰着し先手必敗。
N=5
1枚とった後のxorを0にすることができれば先手必勝。
できなければN=4の場合に帰着する。つまり、「先手が1枚取って後手が1枚取った後に0にできれば先手必敗、できなければ先手必勝」。
少し言い換えると「先手がどの1枚を取っても後手が1枚取って0にできれば先手必敗、できなければ先手必勝」
N=N
1枚とった後のxorを0にすることができれば先手必勝。
そうでない場合、先手がどの1枚を取っても後手が1枚取って0にできれば先手必敗、できなければ$N-1$の場合に帰着。
$ $ここで考察が必要。添字のつけ方は任意であるから分かりやすいようにする。
先手が$A_1$をとったら後手が$A_2$をとって残りのxorを0にできるとする。
$XOR_{i=1}^N,A_i=x,(≠0)$とすると、$A_2 = x;xor;A_1,(≠A_1)$で一意に定まる。
先手が$A_2$をとったら後手は$A_1$をとればよい。
同様に、先手が$A_{2k-1}$をとったら後手が$A_{2k}$をとれば勝てることにする。
$N$が偶数の場合、これを繰り返して$A_{N-1},xor,A_N$までペアリングできるかもしれない。
しかし、奇数の場合は$A_N$が余り、先手が$A_N$を取ったときに後手が勝てる数が割り当てられない。よって、$N$が奇数の場合は「先手がどの1枚を取っても後手が1枚取って0にできる」状態は存在しない。なので、
1枚とった後のxorを0にすることができれば先手必勝。
そうでない場合、先手がどの1枚を取っても後手が1枚取って0にできれば先手必敗、できなければ$N-1$の場合に帰着。
再構成
N=1
先手必勝
N=2
先手必敗
N=3
先手必勝
N=4
1枚とった後のxorを0にすることができれば先手必勝。
できなければN=3の場合に帰着し先手必敗。
N=5
1枚とった後のxorを0にすることができれば先手必勝。
できなければ先手がどの1枚を取っても後手が1枚取って0にできれば先手必敗、できなければ
先手必勝
N=6
1枚とった後のxorを0にすることができれば先手必勝。
できなければN=5の場合に帰着し先手必敗。
まとめ
Nが奇数
先手必勝
Nが偶数
1枚とった後のxorを0にすることができれば先手必勝。
そうでない場合、先手必敗。
Take Home Message
エスパーはしようと思ってできるものではないので、一番基本から順番に考えましょう。