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

(o_o)

ブログ。

AOJ2574 Magical Switches

問題概要
3行3N+1列のマップがあり,同じアルファベットについて,大文字と小文字の一方は全て壁であり,もう一方は通れる床である.左から右まで通れるようにしたいとき,壁にする大文字を全て出力せよ.解が複数あればどれか1つを出力せよ.解がない場合は -1 を出力せよ.

解法
愚直にやると 2^26 * 3 * N なので厳しい.3-SAT に変換して解く.条件が 2^3*N 項くらいになるので,計算量が O(3^8N) くらいになるが,適当に枝刈りすれば通る.オススメの枝刈りは,
・a or b or c の条件を見る際,既に前提として a or b or c が確定しているときは分岐しなくてよい
・a or b or c の条件を a or (not a and b) or (not a and not b c) に変換する
一応入力列をいい感じにソートしたりしたが,効果があったかどうかは知らない.



gistb6ccaff88ab81654bce7