ABC347 D - Popcount and XOR (ゆるい)解説 - 茶処・まっちゃら亭の一休みばしょ

3/31 に開かれたABC347-D問題、解説とは違うことを実装していたので一応ここに書いておきます。

ところで、お久しぶりです

皆さんこんにちは、まっちゃラテです。初めましての方は、初めまして！抹茶大好きな競プロerと認知してくれると幸いです✨
で、皆さんご存じの通り(?)、意地でも緑にまで再び上り詰めた人です。そして次のABCで1年ぶりのHighest更新になりそうです。

今回はABC347-D問題で解説とは違ったことをしていたので、需要ないと思われますがここに記しておきます。

では

※解説は全く持って厳密さを求めず、分かりやすさ重視で書いています。厳密さを求める方は、気を付けて読んでくれると(?)幸いです。

問題(要約)

$a,b,C$ が与えられる。次を満たす整数組 $(X,Y)$ を一つ求めよ。

$0\le X,Y\lt 2^{60}$
$\text{popcount}(X)=a$
$\text{popcount}(Y)=b$
$X\oplus Y=C$

$\text{popcount}(x)$ は $x$ を $2$ 進数に変換したとき、桁に含まれる $1$ の個数を表す(ex. $7=111_{(2)}$ であるので $\text{popcount}(7)=3$ )。また $\oplus$ は排他的論理和を表す。

制約

$0\le a,b\le 60$
$0\le C\lt 2^{60}$

解説(ABC公式)

公式解説では、「 $X,Y$ の $k$ 桁目が $(0,0),(0,1),(1,0),(1,1)$ である個数」を管理してがりがり計算して、場合分けで解くといったことをしています。
しかし、正直に言いましょう。私はこの方法は全く思いつきませんでした。思いつかない代わりに、全探索が思い浮かびました。

では、自分なりの解説を記します。

解説(自分流)

まず、A問題全埋めした私は、 $X\oplus Y=C$ を見て、この問題を思い出しました。

atcoder.jp

この問題の解説を見て重要な教訓を得たことがあったのです。

$x\oplus y=z$ は、 $y=z\oplus x$ と同値変形の関係にある

つまり、この性質を用いることで今回の問題に戻ると $Y=C\oplus X$ と読み替えることができ、さらに次の問題に言い換えることができます。

問題(言い換え)

$a,b,C$ が与えられる。次を満たす $1$ つの整数 $X$ を一つ求めよ。

$0\le X\lt 2^{60}$ ※
$\text{popcount}(X)=a$
$\text{popcount}(C\oplus X)=b$

※ XOR によって桁が増加するわけではないので、 $Y=C\oplus X$ は $2^{60}$ を超えることはありません。実際に $Y$ の最大値を計算すると $2^{60}-1$ (すべてのビットが $1$ のとき)となります。

この問題(言い換え)を解くことを考えます。この言い換えにより、答えに依存するものは $C,X$ のみとなります。 $X$ が定まれば $Y$ が自然と定まるためです。
ここで最初 $X=0$ (すべてのビットが $0$ )としておき、この $X$ を貪欲にビットを立てていくことを考えます。

ではどのように立てていくかというと、まず初心に戻ってビット全探索を考えてみます。今回の制約ではそれでは間に合いませんが、次のように動作をしていることが分かります。ただし $X'$ は $X$ を $2$ 進数に変換したものを表します。

① $C'$ の $i$ 桁目が $0$ のとき $X'$ の $i$ 桁目を $1$ に変える (popcountは増加)
② $C'$ の $i$ 桁目が $1$ のとき $X'$ の $i$ 桁目を $0$ に変える (popcountは変化無し)
③それ以外はpopcountに影響しない

このとき③の部分を見ると、このときが無駄な探索であることが分かります。
よく考えてみると、今回の問題においてビットを立てる順序は関与しないため、①②を貪欲に操作できればいいことが分かります。popcountの減少の操作がありませんが、この $2$ つの操作だけで $\text{popcount}(X)$ が $0,1,2,\dots,59$ の値を取り得るので問題はありません。たぶん。

ここまでまとめると、

$X$ においてビットを立てるか、立てないかを選択する
$Y=C\oplus X$ から $X$ が定まれば $Y$ が自然と定まる
$X$ のビットを立てる順序は関係ない

といった性質が見受けられます。これらより、 $C'$ ( $C$ を $2$ 進数に変換したもの)の $i$ 桁目に一致させるか、異ならせるかを全探索すればよいことが分かり、これなら最悪でも $60\times 60=3600$ 回の処理で終えることができます。
具体的に「 $C'$ の $j$ 桁目が $1$ であるときにおいて $X'$ の $j$ 桁目を $1$ にする個数」、「 $C'$ の $j$ 桁目が $0$ であるときにおいて $X'$ の $j$ 桁目を $1$ にする個数」を定めて愚直に探索をしていくことになります。

そうしてできた $X'$ で popcount を数え、また $Y=C\oplus X$ であるためこれを計算して popcount を数え、それぞれ $a,b$ に一致できるならそれを出力し、一致するものがなかったら $-1$ を出力することで、私はACできました。

元ACコード汚すぎて見せられないです。すみません.... 代わりにちょっとリファクタリングしたものを見せます -> Submission #51900029 - AtCoder Beginner Contest 347

※実際には進数変換もあるのでざっくり [tex:60³=2.2\times 10⁵] 回くらいの処理を要します。すこし定数倍もありますが十分高速だと思われます。
※ビット立てる操作を一回もせずに条件を満たすときもあれば、すべてのビットを立たせることでも条件を満たすことがあることに注意してください(私にはデバッグ大臣が誕生しました)

Epilogue

今回は人生で $2$ 回目の緑diff ACでした。めっちゃうれしい！！！！！！
これからも精進絶やさずに頑張ろうと思います。

解説って分かりやすさを求めるとこんな大変なんよね...でも分かりやすさをさらに砕いて説明するのも...

いいよね！！！！！！！✨

(なんか結構な勢いで間違ったことを言っている場合は、Xで私に言っていただけると嬉しいです)

p

Cは解けませんでした :(