torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces #243, Division 2, B : Sereja and Mirroring

問題概要

 x \times y の行列に対する mirror 操作を、次のように定義する。

  • 結果の行列のサイズは  2x \times y
  • 結果の行列の上半分は、元になった行列と等しい
  • 結果の行列の下半分は、元になった行列の行の順序を反転したもの

 今、サイズ n \times m の行列 a が与えられる。0 回以上の mirror 操作によって a と等しくなる行列 b であって、行数が最小のものの行数を求めよ。

解法

 a より行数の多い行列から a を作ることはできないので、元になる行列の行数は確実に n 以下です。従って、解の存在範囲は [ 1, n ] です。また、b の行数 n' を仮定したとき、b は a の上 n' 行と一致します。従って、a の上 n' 行を取り出して、行数が n 以上になるまで mirror 操作を繰り返せは、a と等しい行列を作れるかどうかを判定できます。mirror の回数は O( \log n' ) なので、計算量的な問題はありません。

コード

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 ]