AtCoder Beginner Contest 172 F - Unfair Nim

公式解説の行間をほぼ埋めました

公式解説の行間埋め

1. 「 a + (a \oplus X) = S

まず XOR の性質を列挙しておきます.任意の非負整数  a, b, c について下記が成立します *1


\begin{aligned}
a \oplus 0 &= a \\
a \oplus a &= 0 \\
a \oplus (b \oplus c) &= (a \oplus b) \oplus c \\
\end{aligned}

早速これらを利用します. a \oplus b = X の両辺に  a \oplus を掛けると


\begin{aligned}
a \oplus (a \oplus b) &= a \oplus X \\
(a \oplus a) \oplus b &= a \oplus X \\
0 \oplus b &= a \oplus X \\
b &= a \oplus X \\
\end{aligned}

と式変形することができ, a + (a \oplus X) = S が成り立つことがわかります.

2. 「動的計画法により実質的に  a の値の全探索を行う」

すみません,よく分かりません…

3. 「 a + b = (a \oplus b) + 2 \times (a \, & \, b)

公式解説に書いてある通り「繰り上がりを無視した足し算」であることを考えて,具体的な整数を使って手を動かせば大体は分かると思いますが,ここでは補足的な解釈を書きます.

 + \oplus を同一視することを考えます.任意の非負整数  a, b を二進表記したときの  d 桁目を  a_{d}, b_{d} とおくと, (a_{d}, b_{d}) = (0, 0), (0, 1), (1, 0) の場合は  a + b = a \oplus b が成立しますが, (a_{d}, b_{d}) = (1, 1) の場合は成立しません.なぜなら, d 桁目は両者とも  0 となり一致しますが  + の場合のみ繰り上がりが発生して  (d + 1) 桁目が  1 増えるという違いがあるからです(逆に言えば, \oplus が「繰り上がりを無視した足し算」であると言えます).よって, + \oplus を同一視することはできません.

しかし, a + b = (a \oplus b) + x が成立するような調整項  x が存在しないか考えてみると,なんと  x = a \, & \, b とすれば成立します. (a_{d}, b_{d}) = (1, 1) であるような全ての  d について「繰り上がりの有無の違い」が発生しますが,裏を返せばそのような位置は  a \, & \, b によって過不足なく拾うことができます.これが理解できれば後は簡単で,繰り上がりが必要なので  2 倍すれば  a \oplus b で無視されていた部分がピッタリ補えるということです(二進表記だから  2 倍).

4. 「 D が非負整数でない場合」

 a + b = (a \oplus b) + 2 \times (a \, & \, b) が成立することから次のことが言えます.


a + b \geq a \oplus b

一か所でも繰り上がりが発生する桁があれば  a + b の方が大きくなり,そうでなければ等号が成立します.(公式解説の記号を使えば)これは  S \lt X のときに成立せず,「 D非負でない」と同値です.

なお, D = \frac{S - X}{2} であるため, S - X 2 で割り切れるか確認する必要もあります.好意的に解釈すると,公式解説ではこのことを含意して「 D非負整数でない」と書いているのだと思われます.

5. 「 D X で共通して立っているビットが一か所でもある場合」

つまり, D \, & \, X = 0 が成立する必要があるということですが,これは具体例を見た方が早いです.


\begin{aligned}
                     a &= 0101100 \\
                     b &= 0111010 \\
S = a + b         &= 1100110 \\
X = a \oplus b &= 0010110 \\
D = a \, & \, b &= 0101000 \\
\end{aligned}

これを観察すると, D X で共通して立っているビットが存在していないことが分かります.そして,これは任意の非負整数  a, b について成立します.正確に言うと「一方でビットが立っている場合,もう一方のビットは必ず立たない」となります.これは  (a_{d}, b_{d}) = (0, 0), (0, 1), (1, 0), (1, 1) 4 通りで場合分けして  a_{d} \oplus b_{d} a_{d} \, & \, b_{d} をそれぞれ計算すれば確認できます(一応,先の具体例にはこの  4 通りが全て含まれています). \oplus & はビットごとに独立に考えられるところがポイントです.

6. 「 X で立っているビットの集合を二分割して得られる整数  Y, Z

例えば下記のように二分割できます.


\begin{aligned}
X &= 0010110 \\
Y &= 0010010 \\
Z &= 0000100 \\
\end{aligned}

つまり, X で立っているビットの集合から二者でビットを一つずつ取り合うことで得られる二つの整数が  Y, Z ということです.「二分割」「一つずつ取り合う」というのを形式的に書くと  Y \, & \, Z = 0, Y \oplus Z = X となります(公式解説に書いてある通りです).

7-1. 「 a = D \oplus Y, b = D \oplus Z というペアは残りの条件を満たします」

「どうやったら  a = D \oplus Y を思いつくか?」という議論は後述します.

まず「残りの条件」が何を指しているかですが,文脈的に下記だと思われます(枠で囲まれた問題文の条件の一つ「 a \leq A_{1}」に言及があるため).


\begin{aligned}
a + b &= S \\
a \oplus b &= X \\
\end{aligned}

ここで, a = D \oplus Y を深堀しておきます. 「 D X で共通して立っているビットが一か所もない」ということはこれまでの議論で保証されており( D \, & \, X = 0),同じことが  Y, Z についても言えます(そのように選んでいるため).よって,実は下記が成り立っています.


\begin{aligned}
a = D \oplus Y &= D + Y \\
b = D \oplus Z &= D + Z \\
Y \oplus Z &= Y + Z \\
\end{aligned}

これを踏まえて,「残りの条件」が成り立っていることは下記のように確認できます(実戦的には具体的にビットを並べれば十分確かめられると思います).


\begin{aligned}
a + b &= (D \oplus Y) + (D \oplus Z) \\
         &= (D + Y) + (D + Z) \\
         &= (Y + Z) + 2 \times D \\
         &= (Y \oplus Z) + 2 \times \frac{S - X}{2} \\
         &= X + (S - X) \\
         &= S \\

a \oplus b &= (D \oplus Y) \oplus (D \oplus Z) \\
                 &= Y \oplus (D \oplus D) \oplus Z \\
                 &= Y \oplus 0 \oplus Z \\
                 &= Y \oplus Z \\
                 &= X \\
\end{aligned}

7-2. どうやったら  a = D \oplus Y を思いつくか?

今やりたいことは「 a + b = S, a \oplus b = X, a \leq A_{1} であるような非負整数ペア  (a, b) のうち, a が取り得る最大の値を求める」です(枠で囲まれた問題文).そのためには少なくとも  a + b = S, a \oplus b = X が満たされるように  (a, b) を上手く決めてやる必要があります. ここで, S S = X + 2 \times D と表現でき,かつ  D \, & \, X = 0 が成り立つことを思い出すと,「 X, D を利用してビットたちを  (a, b) に上手く割り振れないか?( a + b = S, a \oplus b = X を満たせないか?)」ということを考えることができます *2.分かりやすさのため,(先ほどと同じ)具体例を出しておきます.


\begin{aligned}
                     a &= 0101100 \, (※一例) \\
                     b &= 0111010 \, (※一例) \\
S = a + b         &= 1100110 \\
X = a \oplus b &= 0010110 \\
D = a \, & \, b &= 0101000 \\
\end{aligned}

まず  X = a \oplus b を考えると下記が要請されることが分かります.

  •  X_{d} = 1 であるような全ての  d (a_{d}, b_{d}) = (0, 1), (1, 0)
  •  X_{d} = 0 であるような全ての  d (a_{d}, b_{d}) = (0, 0), (1, 1)

意外と自由度がないということが分かりますが,この範囲内で  2 \times D の分のビットたちもカバーして  a + b = S を満たすように  (a, b) を決める必要があります. そしてそれは  (a, b) D を一つずつ配分することでピッタリ満たすことができます.なぜなら, D に相当するビットたちは  a + b では  2 \times D の寄与になる一方, a \oplus b では  D \oplus D = 0 により綺麗にキャンセルするからです( \because D \, & \, X = 0).

以上により,下記のような非負整数ペア  (a, b) a + b = S, a \oplus b = X を満たすことが分かります.そして,これ以外の  (a, b) では条件を満たせないことも同時に分かります( D を一つずつ配分しないと  a \oplus b のときに  X_{d} = 0 が満たせない  d が必ず生じてしまうからです).


\begin{aligned}
a = D + Y = D \oplus Y \\
b = D + Z = D \oplus Z \\
\end{aligned}

8. 「任意の桁は、それより下のすべての桁を合わせたものより重要」

9 節より後に登場する文章ですが,都合により先に取り扱います.

これは十進表記で考えれば,例えば「 1000 > 999〜001 」ということです.二進表記では下位から  d 桁目のビットに着目したとき,それより下位のビットの総和は  2^{d-1} より必ず小さくなる,ということになります.

9. 「まず  Y = 0 として(中略)という貪欲な戦略が最適」

 X で立っているビットを一つずつ降順に取り上げ」というのは,上位のビットから順に見ていくということです.気持ちとしては,ある十進表記の非負整数を二進表記に手計算で変換するとき,上位のビットから順に見て貪欲にビットを立てていくと思いますが,それと似ていると思います.厳密な証明は筆者のレベルを越えそうなので省略します.

所感

Nim とは一体何だったのか… と思うほど,言い換え後の問題文で必要となる考察ステップが多くて非常に難易度の高い問題でした.しかし,一つひとつ整理していけば,これらのほとんどは典型考察であることが分かります.公式解説のように最善手を指し続けるのは難しいので,実戦的には途中で DP や二分探索が入ることはありそうです(そういう解き方も見かけました).

余談ですが,はてなブログの仕様らしく tex でアンド記号が上手く使えなくてストレスが溜まりました(pre タグを使う方法は不格好なので辞めました).試行錯誤した結果,大文字を使うことでそれっぽい見た目になったのでこれで良しとします.「a \, & \, b」のように間隔調整も入れて書いてます.

解答例

https://atcoder.jp/contests/abc172/submissions/22078103

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    ll N; cin >> N;
    VLL A(N); REP(i,N) cin >> A[i];

    ll S = A[0] + A[1];
    ll X = 0; FOR(i,2,N) X ^= A[i];
    ll D = (S - X) / 2;

    // validation
    if ((S - X) % 2 == 1) { COUT(-1); return 0; }
    if (D < 0) { COUT(-1); return 0; }
    if ((D & X) > 0) { COUT(-1); return 0; }
    if (D > A[0]) { COUT(-1); return 0; }

    ll a = D;
    ll L = bitlen(X);
    RREP(i,L) if (BIT(X,i)) {
        if ((a ^ (1LL<<i)) <= A[0]) a ^= (1LL<<i);
    }

    ll ans = A[0] - a;
    if (ans == A[0]) { COUT(-1); return 0; }  // A_1 個未満しか移せない
    COUT(ans);

    return 0;
}

謝辞

ある未定義動作を引き起こして困っていたところをすのーさんに助けていただきました.ありがとうございます.
https://twitter.com/mts1104_ml/status/1386347717220134913

*1:Unfair Nim を解くようなレベルの人たちがこれらを知らないということは滅多にないとは思います

*2:「こうできたらいいな」みたいな「気持ち」的な考察過程でしょうか…