問題

$A, B$ が与えられる。 次のような $\sigma \in \mathfrak{S} _ {2^N-1}$ の存在を判定し、存在するなら構成せよ。

  • $\sigma(0) = A$
  • $\sigma(2^N-1) = B$
  • $\forall i \lt 2^N-1.~ \mathrm{popcount}(\sigma(i) \oplus \sigma(i+1)) = 1$

解法

$A = 0$ かつ $B = 2^k - 1$ と仮定してよい。 グレイコードまずそのまま作り、これを 2-opt のようにして変形すればよい。 計算量は不明だが $O(N^2 2^N)$ ぐらいで間に合う。 非想定ぽい。

考察過程

  1. それぞれに排他的論理和をして $(A, B) \gets (0, A \oplus B)$ と更新してよさそう (簡単化)
  2. 条件はグレイコードみたいになってる (知識)
  3. $\mathrm{popcount}(B) = 1$ なら自明 (部分問題)
  4. ちょうど $1$ bit 変わるので $\mathrm{popcount}(B)$ は奇数でなければならない (不変量) (必要条件)
  5. この必要条件はたぶん十分条件になってる (推測)
  6. 「$0$ から始まるグレイコードのような系列であって $B$ で終わるものを構成せよ」を解けばよい (帰着)
  7. グレイコードの末尾をいくつか反転させることで末尾を操作できないか (推測) (嘘)
  8. 「$0$ から始まるグレイコードのような系列であって奇数 $k$ に対し $2^k-1$ で終わるものを構成せよ」を解けばよい (帰着)
  9. 現在の末尾が $00001$ で、これを $00111$ にしたいとする。 $00111$ の前後に $00011$ か $00111$ があれば 2-opt のように継ぎ換えてよい。前後が $01111$ と $10111$ の場合は詰みだが、他に $11001$ への遷移とかを試せばよい。 $11111$ は代替を持たないが、最大なのでそういう問題はない。 (嘘)
  10. 嘘だったけど乱択で焼きなましぽく上手く誤魔化したら通った (終)

バグ

  • (k << 1) - 1 を b に組み換えるようなことをしたくて 2 重ループを回したときに嘘の i < j を仮定してしまった
  • ! ! (x & (1 << i) == ! ! (x & (1 << j) とすべきところで (x & (1 << i) == (x & (1 << j)
  • 1 << n のつもりで n << 1 と書く

感想

結局乱択で誤魔化したので実質解けてない。 やたらバグらせた。ブランクを感じる。

想定解は $N$ に関する帰納法。 特に任意の $A, B$ に対して成立するように強めたもの。 初手の簡単化のあたりがまずかったということらしい。

リンク