AtCoder Beginer Contest 086 - D
- AtCoder Beginer Contest 086 - D Checker
- 市松模様(黒・白)を与えられた数値Kで描画する
- 入力として(x,y)と色(黒・白)が与えられるので、入力値で塗りつぶせる最大数を求める
解説
領域に属する座標をどうやって最大化するか?
(方針) 解説より
- マス (x, y) が白 と マス (x, y + K) が黒 は同値なので、(x, y,′ W′) という入力を (x, y + K,′ B′) に置き換えても条件は同じです。これで入力の ci を全て’B’ に変換することが出来ます。
- マス (x, y) の色とマス (x, y + 2K),(x + 2K, y) の色は一致します。なので、入力の x, y を x%2K, y%2K で置き換えても答えは変わりません。すると 0 ≤ x, y < 2K と変換することが出来ます。
なるほど…これを考えると、黒だけ考えればよくなるので領域探索の次元が減り、入力座標の数値も小さく収まる
満点解法の解説
(手順1)
- 入力値の白を黒に変換し、入力値を2Kで割った余りに変換することで小さくする
- O(N) ぐらい?
lines = <<'EOS' 4 3 0 1 W 1 2 W 5 3 B 5 4 B EOS #lines = $stdin.read array = lines.split("\n") N,K = array[0].split(" ").map(&:to_i) coords = array[1..N+1].map do |str| x,y,color = str.split(" ") x,y = x.to_i,y.to_i x,y,color = x,y+K,'B' if color == 'W' x,y = x%2*K,y%2*K puts "#{x},#{y},#{color}" [x,y,color] end p coords
(手順2)
問題は上の手順で簡単化された
- x = [0,2K), y = [0, 2K) の範囲に座標が与えられる(上のコードの coords がそれ)
- その範囲を正方形 K x K で走査し、正方形の内包する点の数が最大化するところを求める、答えは□に入る点の数の最大値でよい
- どうやら線形探索でもいける計算量らしいが、二次元累積和を使おう