pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Gray Code

ICPC 2017 国内予選D: 弁当作り

問題の解説はせずに、グレイコードの紹介をする。iに対してi^i>>1を計算して列挙すると、隣接する値のハミング距離が 1 になる。これをグレイコードと呼ぶ。 0000 => 0000 0001 => 0001 0010 => 0011 0011 => 0010 0100 => 0110 0101 => 0111 0110 => 0101 0…