トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 086

[競技プログラミング,競プロ解説]

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