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

CODE FESTIVAL エキシビジョン Trax

赤色を1, 白色を0とする。すると4種類のコマは

 0    0    1    1  
0 1  1 0  0 1  0 1 
 1    1    0    0  

となる。要するに、左右と上下は独立。

ここで、線がつながってることに注目。すると、とある列/行だけ取り出した時の値は

0 1 1 0 0 1 1 0 0 1 ... みたいになってる。つまり最初が0か1かでその列は一意に決まる。

よって、本質的には長さHの数列 a_i とWの数列 b_i だけを考えれば良い。値は0か1だけである。

よって、サイクルがあるとNGという条件を無視すると、答えは 2H+W.

ここで、"サイクルがある"と"長さ4のサイクルがある"は同値であることに注目。証明は略。

そして、"長さ4のサイクルがある" と "a_i = a_i+1, b_j = b_j+1, ((a_i) + j) % 2 == ((b_j) + i) % 2, なるi, jが存在"は同値であることが示せる。

あとはちょっと実装が重いDP。