AGC031 C - Differ by 1 Bit
解法
コンテスト本番で私が考察・実装した方針を書いていきます。公式解説とは実装の方針が異なっていて、公式解説のほうが恐らく楽な実装だとは思いますが、ACを得るまでの1つの過程として参考になればと思います。
YES/NO判定
まずはここから。数列が1つ進むごとにビットが立っている個数が または
されること、数列の長さが偶数であることから、最初の要素と最後の要素でビットが立っている個数の偶奇は必ず異なっているはずです。なのでもし
でビットが立っている個数の偶奇が一致していれば、問答無用で
NO を出力すればよいです。
では偶奇が異なっている場合には必ず問題の条件を満たす数列が存在するでしょうか。なんとなく存在しそうな気がします（本番ではここで のときの
全列挙コードを書きました）。それはこれから具体的に構成していくことで示していきます。
考えやすい形への帰着
以降、「数列の隣り合う要素は2進表記でちょうど1桁だけ異なる」ことを単に「条件を満たす」と表記します。
まず、スタートもゴールも変数だとややこしいのでスタートを にします。条件を満たす数列
は全ての要素に
を掛けてもやっぱり条件を満たします。そのため
として、条件を満たす数列
を構築すれば、その全ての要素に
を掛けて復元したものが答えになります。これでスタートを
に固定できます。
さらに のビットが散らばっていると考えにくいので、ビットの位置を並び替えて上位ビットに
を固めます。たとえば2進数で
に対して、ビット列を並び替えて
とします。これも後で位置を戻して復元します。
これらの操作によってこの問題は、スタートは 、ゴールは
（1の個数は奇数で、
の1の個数と同じ）であり条件を満たす数列を構成する問題に帰着することが出来ます。
構築
構築のアイデアは以下の通りです。
図のように「 で始まるもの全部」「
で始まるもの全部」…という風に列挙しながら、一番上の桁を1つずつ
にしていきます。上からビットを固めていくので、最後まで影響を受けない一番右側のビットを調整に使います。
このように構築すると、ゴールの の個数が奇数であれば必ず
通りの全ての値を尽くしてゴールにたどり着くことができます。
この構築をする上で必要なのは、図中青破線で示しているところで使う「 通りの数を尽くし、隣り合う要素はちょうど1ビット異なっていて、
で始まり
で終わるような数列」もしくはその逆順です。
これは再帰的に作ることが出来て、長さ のときの数列が得られているとすると
- 長さ
のときの数列を2倍したもの
- 長さ
を結合することで長さ のときの数列を得ることが出来ます。例えば
から上記の方法で長さ8の数列を作ると
となります。
仕上げ
以上の方法で、スタートは 、ゴールは
であり条件を満たす数列を構成することができました。
最後にビットの位置を戻して、全要素に を掛ければ元の問題に対する答えが求められます。
