問題概要
の行列に対する mirror 操作を、次のように定義する。
- 結果の行列のサイズは
- 結果の行列の上半分は、元になった行列と等しい
- 結果の行列の下半分は、元になった行列の行の順序を反転したもの
今、サイズ の行列 a が与えられる。0 回以上の mirror 操作によって a と等しくなる行列 b であって、行数が最小のものの行数を求めよ。
解法
a より行数の多い行列から a を作ることはできないので、元になる行列の行数は確実に n 以下です。従って、解の存在範囲は [ 1, n ] です。また、b の行数 n' を仮定したとき、b は a の上 n' 行と一致します。従って、a の上 n' 行を取り出して、行数が n 以上になるまで mirror 操作を繰り返せは、a と等しい行列を作れるかどうかを判定できます。mirror の回数は なので、計算量的な問題はありません。
コード
getInts = map ( read :: String -> Int ) . words <$> getLine main = do [ h, w ] <- getInts rows <- replicateM h getInts let mirrors rs | length rs < h = mirrors $ rs ++ reverse rs | otherwise = rs print $ head $ filter ( ( == rows ) . mirrors . ( flip take rows ) ) [ 1 .. h ]