AtCoder Grand Contest 031：C - Differ by 1 Bit
問題
解法
１回の操作でどこか１つの bit を反転させるので，A と B の立っている bit 数の偶奇は必ず違う．なので，偶奇が同じ場合は必ず操作を構成できないので NO．逆に偶奇が異なる場合は必ず構成できる．
再帰的に構成を求めていく．まず，A と B で異なる bit が必ずある（A != B なので）．その bit の桁を k とすると，A, B の k-bit 目を削除した (N - 1) bit の数をそれぞれ C, D とおくと，C, D の立っている bit 数の偶奇は，前の動作で異なる bit を削除したので，必ず等しい．ここで，C, D と立っている bit 数の偶奇が異なる数 E (C <= E <= D) をおく．これは C のどこか（どこでもいい）の bit を反転させることで作れる．すると，C ~ E で操作を構成することができ，また，E ~ D でもできる．これら２つの順列の k-bit 目に A, B の k-bit 目をそれぞれ追加すれば A ~ B の操作を構成することができる．実装では，C ~ E, E ~ D それぞれの両端を A, B として上の処理をしていく．区間の長さが 2^1 になったときの操作は自明に (A, B) になる．O(N^2 * 2^N)．
解答
解説を読んでも理解できず，解くまでかなり時間がかかった．解法さえわかれば実装はそんなに重くないと思った．
