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 で走査し、正方形の内包する点の数が最大化するところを求める、答えは□に入る点の数の最大値でよい
- どうやら線形探索でもいける計算量らしいが、二次元累積和を使おう