ABC172 F. Unfair Nim - phyllo’s algorithm note

問題

石の山がN個あり、i番目の山にはA_i個の石がある。
2人で「交互に、石の山を一つ選び、そこから1個以上の石を取り除く。先に取り除くことができなか唸ったほうが負け」というゲームを行う。

このゲームは、2人が最適に考動する場合、ゲーム開始時にどちらが勝つか判定できるが、ここで、1番目の山から0個以上A_1個未満の石を2番めの山に移すことができ、後手が必勝になるようにしたい。

このようなことが可能な場合、移動する石の個数の最小数を、不可能な場合は-1を出力せよ。

制約

2 <= N <= 300
1 <= A_i <= 10^12

解法1

上記のゲームはNimで、すべてのA_iのxorを取った値が0ならば後手が勝てる。

石を移した後の1番目の個数をa、2番目の個数をbとする。

Nimの条件から、A_3 xor ... xor A_N = Xとすると、条件は「a xor b xor X = 0」で、Xを右側にうつすと「a xor b = X」でないといけない。

他の条件として、問題文から、1番目から2番目にいくつ移してもその合計の石の数は変化しないので、「a + b = A_1 + A_2 = S」と書ける。

また、1番目の山からは0個以上A_1未満なので、「0 < a <= A_1」でないといけない。

よって、求めるものは、
a xor b = X
a + b = S
0 < a <= A_1
を満たす最大のa、ということになる。

一般に、和とxorは「a + b = a xor b + 2 * (a and b)」という関係式が成り立つため、この式から、「S = X + 2 * (a and b)」=>「a and b = (S - X) / 2」が成り立たないといけない。
S-Xが奇数の場合は等式が成り立たないので、不可能。

a and b = Dとしておくと、D(andの条件)とX(xorの条件)はそれぞれビット単位での条件なので、ビットごとに見れる。

各ビットについて、DとXのビットからa,bのビットの組み合わせを考えると、
(0,0) => aもbも0じゃないといけない
(0,1) => aとbは(0,1)か(1,0)が可能
(1,0) => aもbも1じゃないといけない
(1,1) => aとbの組み合わせはありえない
という条件でなければならないことがわかる。

したがって、DとXでどちらも1になっているビットがある場合は、不可能。
それ以外の場合は、DとXが(0,1)になっている場合だけa側を1にするかb側を1にするかの選択肢がある。

aは、「0 < a <= A_1」を満たす必要があるので、A_1以下になるよう最大のaをDとXのビットの条件を選びつつ求めれば良い。

まず、DとXが(1,0)の場合はaもbも1じゃないといけないことから、Dで1が立っているビットはすべてaでも1にしておく。
このときすでに「0 < a <= A_1」を満たせないならば、不可能。

そうでないならば、DとXが(0,1)のところで、A_1を超えないように1か0を選べるが、これは、上位ビットで1を選ぶのはそれより下位のビットで1を選ぶよりも大きい値にできることから、貪欲に上位ビットから「入れた場合にA_1を超えないかどうか」をチェックして、超えないなら入れていく、という方法で求めれば良い。

最終的に、aが0になってしまう場合は、不可能。そうでなければ、A_1 - aを返せば良い。

(全体の流れは、条件式を取り出す→式変形→ビットごとに見る→最大化するため上位ビットから貪欲に選ぶ)

解法2

途中までは解法1と同じで、
a xor b = X
a + b = S
0 < a <= A_1
を満たす最大のaを直接的に求めたい。

これはあるビットについて考えると、それより下位ビットで最大のものだけわかれば十分そうというものから、桁DPを考える。

条件を状態として持つように考えると、各ビットについては、そのビットと下位ビットからの繰り上がりを考える必要があるので、
dp[i][j][k] := 下からi桁目までで、繰り上がりをしているか(j=0,1)とA_1以下かどうか(k=0,1)の条件のときの、最大のa
というものが考えられる。

今、i,j,kでループを回している場合、aとbのビットの組み合わせ(4通り)を考える。
このとき、
xorを取った値がXのそのビットの値を一致しない場合はスキップ。
和(jとaとb)を取った値がSのそのビットの値を一致しない場合はスキップ。
和を取って桁上りがある場合は、次の状態はj=1に遷移、そうでなければj=0に遷移。
A_1以下かどうかは、A_1のビットと比較して、「aが1、A_1が0」ならば満たせていない、「aとA_1のビットが同じ」なら状態は継続(次の状態もkになる)、「aが0、A_1が1」ならば満たす。
とできるので、これで遷移先で最大値を保持するよう回せば良い。
最終的な答えは、dp[最大ビット][0][0]で、これが存在しない場合や0の場合は許されないので、不可能。そうでなければA_1-dp[最大ビット][0][0]を返せばよい。