読者です 読者をやめる 読者になる 読者になる

「今週のお題:十文字に反転して色を揃えて!」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 標準入力から空白区切りで与えられる m,n に対して、白もしくは黒の2色からなる横mマス、縦nマスのマス目を考える。
  • 各配置における、全マス目を同じ色にするための最短手順の中で、最長の手数を出力する。( ただし、同じ色にすることができない配置は除外する )
  • 1手順で行える操作は、あるマスと、それに隣接する縦・横のマス ( 領域外に出る分は除く ) を全て白黒反転させる、というもの。
  • なお、テストケースは $mn\le 18$ を満たす。

例えば次の画像は、m=4,n=4 の場合、3手で同じ色にできる配置と、何手かけても同じ色にできない配置を表すものです。

https://codeiq.jp/sites/default/files/answer_ready/2972/q51.png

解説

まず、ある手順で全て同じ色にできる場合、選ぶマスの順序を取り換えたとしても、やはり同じ色にできます。なおかつ、同じマスを反転対象として2回選んでも反転が取り消されるだけなので、最短手順のみを扱う以上、複数回選ぶことを考える必要はありません。

ということは、手順ではなく、あくまで反転対象のマスの組み合わせを考えるだけで済みます。

ここで、手順を逆に辿って 「全て白から始めて、どのマスを反転させるか $2^{mn}$通りの反転を試し、初期配置毎の手数を調べる」ということをしました。 マス目の状況は$mn$ビットの2進数とみなし、色を反転させるという操作を xor により処理します。

この考えだと、自動的に「全てを白にできない配置」を除外できます。

なお、異なるマスの組み合わせでも、同じ初期配置になるものがあります。そのため、同じ初期配置でもより短い手数の組み合わせが現れた場合は、手数の情報を更新していきます。
このようにして、各初期配置から全て白へ変化させるための最小手数が求められます。

ただし、同じ色であっても、全て白ではなく全て黒へという変化も調べる必要があります。つまり、ある初期配置については、全て白にするよりも、全て黒にした方が、手数が少なくなる可能性があるのです。

とはいえ、全て白にすることを考えるのに対して、単純に全ビットを反転させて考えれば済むため、初期配置毎の最小手数を登録する際に、ある代表マスが必ず白になる ( 代表ビットが 0 になる ) ように補正することで、両方同時に扱うようにしました。

具体的には、例えば m=4,n=3 のケースで、

  • 101000011111 を 000000000000 ( 全て白 ) にする最短手順は 7手
  • 一方、ビット反転した 010111100000 を 000000000000 にする最短手順は 3手
  • ということは、10100011111 は、111111111111 にするのが3手ということなので、000000000000 にするより手数が短い

という状況が発生します。ここで、101000011111 を 7手と登録してしまうと、111111111111 にする3手を捨ててしまうことになります。
なので、代わりにビット反転して最下位ビットを0にした、010111100000 を7手だとみなします ( 101000011111 の分は登録しない )。そうすると 010111100000 → 000000000000 の3手と競合するため、7手の方が捨てられ、短い手数の方が正しく生き残る、という寸法です。

提出したのは次のRubyのコードでした。

m,n=gets.split.map(&:to_i)
d=m*n
mask=(1<<d)-1
a=(0...d).map{|i|
  x=i%n
  ((((7<<(x-1))&((1<<n)-1))<<(i-x)|1<<(i-n)|1<<(i+n)))&mask
}
h={0=>0}
f=->i,x,s{
  y=x^a[i]
  z=y^(mask*y[0])
  h[z]=s+1 if !h[z]||h[z]>s+1
  return if i>=d-1
  f[i+1,x,s]
  f[i+1,y,s+1]
}
f[0,0,0]
p h.values.max

終わりに

最初は、各ビット反転のパターンをGF(2)のベクトルとみなし、基底とそれ以外により分けてハミング距離を考えたら…とか思ってたのですが、上手くいくビジョンが思い浮かばなかったため、素直に全探索することにしました。なんか良い方法があったんでしょうかね?