No.274

ブロックをそのまま積んでみて, 左から $i$ 列目と右から $i$ 列目の色の数を数える.

色が3個以上あればどうしても良い壁にはできない.

…というやり方で通ってしまったのだが, これだと色が2個以下のときに良い壁にできるという証明をしていない.

そこで, 2-SAT を使う.

$i$ 番目のブロックを180度回転させるかどうかを $a_i$ とする.

$i$ 番目のブロックと $j$ 番目のブロックが回転させない状態で重なる場合は, $(a_i \lor a_j) \land (\lnot a_i \lor \lnot a_j)$ という制約条件になる.

$i$ 番目のブロックと $j$ 番目のブロックが片方を回転させた状態で重なる場合は, $(a_i \lor \lnot a_j) \land (\lnot a_i \lor a_j)$ という制約条件になる.

(回転させても回転させなくても重なる場合はそもそも良い壁にはできない)

この制約条件を 2-SAT で解けばいい.