人権なし

競プロで解いた問題や開発の進捗などの記録です

AtCoder Grand Contest 031:C - Differ by 1 Bit

問題

atcoder.jp

解法

1回の操作でどこか1つの 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 でもできる.これら2つの順列の k-bit 目に A, B の k-bit 目をそれぞれ追加すれば A ~ B の操作を構成することができる.実装では,C ~ E, E ~ D それぞれの両端を A, B として上の処理をしていく.区間の長さが 2^1 になったときの操作は自明に (A, B) になる.O(N^2 * 2^N).

解答

atcoder.jp

解説を読んでも理解できず,解くまでかなり時間がかかった.解法さえわかれば実装はそんなに重くないと思った.

f:id:babcs2035:20190317161054p:plain