ABC 172 F - Unfair Nim

提出したコード

前提知識として、Nimというゲームであることを知っておくと良い。Nimには必勝法があり、すべての山の石の数 $A_i$ についてXORをとり、その結果が0以外であれば、その手番の人が最適な動きを取れば必ず勝つ。 必勝状態であるXOR != 0で手番が回ってきたとき、ある山からある数の石をうまく取り除くと、XOR = 0の状態に遷移できる。 逆に、XOR = 0の状態からは、どんな選び方をしても、必ずXOR != 0 の状態（必勝状態）に遷移してしまう。 ターンの経過に伴って石の数の合計は減っていくので、必ずゲームは終わる。 Grundy数というらしい。

これをふまえて、考察を進める。「1番目の山から0個以上$A_1$個未満の石を2番目の山に移すことで …」とあるので、先頭二つの山についてのみ考えればよいことがわかる。なので、これ以降$A=A_1$、$B=A_2$、$X = A_3 \oplus A_4 \oplus \cdots \oplus A_N$とする。また、”移す”という操作を$A$を$a$、$B$を$b$に変更すると言い換える。そうすると、以下の条件を満たしつつ、できるだけ$a$を大きくすればよい（”移す”石の数が最小）ということになる。

これは桁DPによって解くことができる。$dp_{i,j,k}$を、下から$i$桁目まで見たときの$a$の最大値とする。 ただし、一つ上の桁に対して繰り上がりがある場合は$j=1$、$i$桁目まで見たときに$a$が$A$を上回っていれば$k=1$とする。 50桁くらいまで見れば十分。

提出コードにコメントをつけておく。初期値は以下の通り。

rep(a, 2) {
  ull b = a ^ (X & 1); // b は a から決まる
  ull carry = a & b;
  ull _sum = a ^ b;
  if (_sum != (S & 1)) continue; // そもそも合計がS出なければスキップ
  ull over = a > (A & 1);
  chmax(dp[0][carry][over], a);
}

dp[i][j][k]からの遷移は以下の通り。配るDPなので i + 1 桁目について見ていく。

rep(i, M-1) rep(j, 2) rep(k, 2) rep(a, 2) {
  if (dp[i][j][k] == -1) continue;
  ull ni = i + 1;
  ull b = a ^ ((X >> ni) & 1); // b は a から決まる
  ull _sum = (a + b + j) & 1;  // 合計を計算する場合には下の桁からの繰り上げを考慮する
  ull _carry = ((a + b + j) & 2) > 0; // ni+1 桁目に対して、繰り上げがあるかどうか求める
  if (_sum != ((S >> ni) & 1)) continue; // そもそも合計がS出なければスキップ
  ull over;
  if (a >  ((A >> ni) & 1)) over = 1; // ni桁目まで見たとき、a が A を上回っているかどうか求める
  if (a <  ((A >> ni) & 1)) over = 0;
  if (a == ((A >> ni) & 1)) over = k;
  chmax(dp[i+1][_carry][over], dp[i][j][k] | (a << ni)); // dpを更新
}

自力では解けなかった。解説動画が分かりやすくて本当に助かっている。