E - Xor Annihilation Editorial by yuto1115
シミュレーションを用いた解法シミュレーションを用いた解法です。ただし、愚直なシミュレーションは間に合わないため、「確実に合体することが分かる要素」を順に合体していくことを考えます。
以下、正整数 \(a\) に対して、\(a\) の \(k\) bit 目が \(1\) であるような最大の \(k\) を \(top(a)\) と表記します。
今、\(top(w_i) \ (1\leq i\leq |w|)\) の最大値を \(M\) とし、\(top(w_i)=M\) を満たす \(i\) を小さい順に \(i_1,i_2,\dots,i_k\) とします。\(w\) の総 xor が 0 であるため、\(k\) は偶数です。ここで、以下の事実が成り立ちます。
- \(Z\) の \(M\) bit 目が \(1\) ならば、\(w_{i_1}\) は \(-100^{100^{100}}\) に達するまで左に動き続けてしまう。
- \(Z\) の \(M\) bit 目が \(0\) ならば、\(w_{i_1}\) は右に、 \(w_{i_2}\) は左に動き、いずれ両者およびその間の要素は合体する。同様にして、\(w_{i_{2l-1}}\) と \(w_{i_{2l}}\ (1 \leq l \leq \frac{k}{2})\) およびその間の要素がそれぞれ合体する。
証明は、「各 \(w_i\) はそれぞれ、\(L\) と \(R\) のうち \(M\) bit 目が \(1\) である方向に動き出すこと」及び「動く過程で \(top(w) < M\) であるような要素 \(w\) と合体したとしても、動く向きは変わらないこと」から従います。
よって、\(Z\) の \(M\) bit 目は \(0\) でなければなりません 。逆にこれが成立すれば、\(w_{i_{2l-1}}\) と \(w_{i_{2l}}\ (1 \leq l \leq \frac{k}{2})\) およびその間の要素はいずれ必ず合体するので、今合体してしまっても問題ないです。
すると、\(M\) が \(1\) 以上小さくなった問題に帰着されました。このシミュレーションを繰り返していくと、\(N\) 回以内で \(w\) の全ての要素が \(0\) になるので、そこでシミュレーションを終了します(全てのボールが停止したことを意味します)。
シミュレーション中における \(M\) として表れなかった bit については、\(Z\) に関する制約はないため、単に答えを \(2\) 倍すれば良いです。
計算量は \(O(n2^n)\) です。
実装例 (C++) : https://atcoder.jp/contests/arc152/submissions/36685431
posted:
last update: