ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Xor Sum　Editorial解法の「解説の解説」

AtCoder プログラミング 競技プログラミング

D - Xor Sum

重み付き配点のABCで出された問題としては最強候補の1つと言われている「Xor Sum」。ビット単位のXOR演算と整数の足し算の密接な関係を利用した問題で、様々な解法が考えられています。こちらの記事ではいくつかの解法がまとめられています。

Xor Sum(ARC066 D)についてのいろんな解法 - Qiita

問題自体の難しさもさることながら、公式解説PDFも行間を補って読み解く必要がありなかなか大変です。この記事では「解説の解説」、つまり公式解説PDFの解法を色々と補足しながらもっと丁寧に解説することを試みます。

記法

整数の2進数表記におけるビットの位置について、一番下を0番目として下から d 番目のビットを単に「 d ビット目」と呼ぶことにします。 d ビット目は 2^{d} の位に相当します。

非負整数 a, b のXOR演算を記号 a \oplus b で表記します。

XOR演算と足し算の関係

まずはここからです。XOR演算は、繰り上がりのない足し算と思うことが出来ます。これは非負整数 a, b のXOR演算と足し算それぞれについて、 a, b の d ビット目の組み合わせが演算結果にどう影響するかを比較してみると分かります。

a, b の d ビット目 a \oplus b への影響 a + b への影響
0, 0 d ビット目が0になる d ビット目が0になる
0, 1 または 1, 0 d ビット目が1になる d ビット目が1になる
1, 1 d ビット目が0になる d ビット目が0になり、 d+1 ビット目に1繰り上がる

このように繰り上がりの有無を除いて2つの演算結果は同じになります。また繰り上がりの有無の違いから、 a \oplus b \le a+b が必ず成り立ちます。

この性質を用いると問題が少し考えやすくなります。 u = a \oplus b, v = a + b について u \le v という関係が必ず成り立つので、 v \le N ならば自動的に u \le N となります。これで 0 \le u, v \le N という条件について注意するべきは v のほうだけであり、 u のほうは気にしなくてもよいことが分かりました。

(u, v) の数え上げから (a, b) の数え上げへ

(a, b) に計算を施した結果である (u, v) の数え上げというものはなかなか難しいです。これを直接考えようとすると、計算結果のほうに何か特別な構造を見つけたりする必要があります。（冒頭リンク先の「シェルピンスキーのギャスケット」解はまさにそういうアプローチです）

一方、仮に (a, b) のほうを数え上げ対象にしてみたらどうでしょうか。もし「非負整数の組 (a, b) のうち、 u = a \oplus b, v = a + b について○○な条件を満たすような組の個数がいくつあるか求めよ」という問題であれば、 (a, b) について全探索を考え高速化したり、DPを回すなどの方法が取れます。できればこちらを考えたいです。

ただ実際には (a, b) と (u, v) は1対1に対応しないため、 (u, v) の数え上げ問題を直接 (a, b) の数え上げ問題に言い換えることはできません。例えばあるペア (a, b) と、それに対して「 a, b 間で同じ桁のビットを交換する」という操作を何度か行ったものでは、XORも和も同じ値になります。

f:id:betrue12:20190206223308p:plain

ではこの「同じ桁のビットを交換」パターン以外で、異なる (a, b) から同じ (u, v) ができてしまうことはあるでしょうか？結論を書くと、これはありません。それを確認します。

異なる p_{1} = (a_{1}, b_{1}), p_{2} = (a_{2}, b_{2}) に対してまずXORが一致、つまり a_{1} \oplus b_{1} = a_{2} \oplus b_{2} になっていると仮定しましょう。このとき p_{1}, p_{2} で異なっている桁のうち「同じ桁のビット交換」でないものは、必ず「片方が (0, 0) でもう片方が (1, 1) 」の形になっています。

f:id:betrue12:20190206222912p:plain

このときに和のほうがどうなるか考えます。 d ビット目について「片方が (0, 0) でもう片方が (1, 1) 」という状態になっている場合、その違いによって a_{1} + b_{1} と a_{2} + b_{2} の間には \pm 2^{d+1} の差が生まれます。これらがキレイに相殺されて a_{1} + b_{1} = a_{2} + b_{2} となってしまうと同じ (u, v) ができてしまうのですが、それは起こり得ません。各桁で生じる差たち 2, 4, 8, 16, ... からどのように選んで符号を付けても、1つ以上選んでその合計が0になることはないからです。

これで「同じ桁のビットを交換」パターン以外で、異なる (a, b) から同じ (u, v) ができてしまうことはないと確認できました。これまでの考察から問題を次のように言い換えることが出来ます。

  • 非負整数 (a, b) の組について、 a+b \le N である組の個数を求めよ。ただし「 a, b 間で同じ桁のビットを交換する」という操作を何度か行って一致するものは1個として数えることにする。

これは元の問題の数え上げ対象と1対1の対応が取れているため、正しい問題の言い換えになっています。また数え上げ対象が (a, b) になっているため考えやすくなっています。

※公式解説PDFはいつの間にかこの言い換えがされていて、それが可能な理由は完全に省略されていますね…

桁DPを考える

ではこの問題を解いていきましょう。同じ桁のビットを交換したものは同一視するため、各桁ごとのビットの選び方は (0, 0), (0, 1), (1, 1) のいずれかになります。桁ごとにこの3パターンの選び方があり、 a + b について上限が存在する…少し変則的ですが、これは桁DPが有効であるような形をしています。

※2進数での桁DPで解ける問題はちょうど先日のABC117でも出題されたので、そちらの解説も参考にしてみてください。

基本的な考え方に従えば、「 d ビット目まで上から見て、その時点で a+b \lt N であることが確定している/いない選び方の数」みたいな状態を考えたくなりますが…これを普通にやると失敗します。単に1つの整数の各桁の値を決めていく場合は上の桁で上限より小さいことが確定すれば下の桁は自由に選べますが、今回の場合 (1, 1) を選んだ際に繰り上がりが発生してしまうからです。

単に「 d ビット目まで上から見て、その桁までの値において a+b が N より小さい」だけでは情報として不十分です。となれば、いくつ小さいかを具体的に持つことで桁DPができないでしょうか？

「 d ビット目まで上から見て、その桁までの値において a+b が N より s \times 2^{d} だけ小さい」ような場合の数を dp\lbrack d \rbrack\lbrack s \rbrack とします。この s が多ければ多いほど、下の桁で繰り上がりがあっても N を超えにくくなります。また s \lt 0 である場合は a+b \gt N であることが確定してしまうので、そのような状態には遷移しないことにします。

dp\lbrack d+1 \rbrack\lbrack s_{d+1} \rbrack、すなわち d+1 ビット目まで見た時点で a+b が N より s_{d+1} \times 2^{d+1} だけ小さい状態からの遷移を考えます。ここから見る桁を1つ下ろすと 2s_{d+1} \times 2^{d} だけ小さいことになるので、 s の値は見る桁を1つ下ろすと2倍になって引き継がれます。

ここに N の d ビット目と、 (a, b) の d ビット目として選んだ値が足し引きされます。これらをそれぞれ n_{d}, k_{d} とすると、 d ビット目における s_{d} は

s_{d} = 2s_{d+1} + n_{d} - k_{d}

と計算できます。 n_{d} は入力 N によって決まる値であり、 a, b のビットの選び方が (0, 0), (0, 1), (1, 1) であることから k_{d} = 0, 1, 2 の3通りについてそれぞれの dp\lbrack d \rbrack\lbrack s_{d} \rbrack に遷移します。

これを s \ge 0 の範囲で全て回せば答えを求めることが出来ます。

計算量を削減する

ただしこのDPをそのまま回すと、一番下の桁まで到達した時には s は最大で N と同じ値まで膨れ上がります。1つ1つ遷移を計算していては間に合いません。

ここで式を見返してみます。 n_{d} は0か1、 k_{d} は0, 1, 2のどれかであり、 s_{d+1} は2倍されています。となると s_{d+1} が十分大きいところでは s_{d} \ge s_{d+1} が成り立ちそうです。

具体的には s_{d+1} \ge 2 であれば必ず s_{d} \ge 2 になります。これは「上位のある桁で s \ge 2 となってしまえば、後の桁をどのように選んでも以降は s \ge 2 がずっと保証される」ということを意味します。となると2以上であることが分かれば、その具体的な値を区別する必要はありません。

このことから、 s として持つべき状態は「0」「1」「2以上」の3通りだけで良いことが分かります。ここまで状態を削ることができれば、各桁においては s の3状態と k_{d} の3通りの組み合わせについて遷移をすればよいので、（桁数）×9回の遷移でDPを完了することが出来ます。これで計算が間に合い、問題を解くことができました。

ACコード

（C++）Submission #4186608 - AtCoder Regular Contest 066

感想

というわけで「解説の解説」を書いてみました。公式解説の記述は半ページほどですが、ちゃんと言い換えの妥当性や具体的な遷移まで含めて書くとこれほどの分量になりますね…

私自身、この問題はABCを埋めているときにあまり深く理解をしないまま解説ACをした記憶があります。当時よりは間違いなく実力が上がっているため、今回改めてこの解説を書いてみて解法をしっかり理解できた気がします。

この記事が皆さんのACに繋がれば幸いです。読んでいただきありがとうございました！