🍡

[鉄則B09] Papers

2024/04/28に公開

Ruby

差分の累積和のひっかけ問題。

問題を要約する

何枚かの紙を配置したときの紙の総面積は？
紙は重なっていることもある

ひっかけポイント1

座標は点を表している

つまり (0, 0) - (2, 2) の紙の面積は 3 x 3 ではない。

ひっかけポイント2

座標はもとから 0-based

入力例の最低値が 1 だったことから、いつものように 1-based だと早とちりしてしまった。

解き方

範囲の隅の四点を±1するのを枚数分繰り返す
最後にまとめて1回だけ累積和テーブルを作る
値が 1 以上の個数を求める

例1でシミュレーション

(x1, y1) - (x2, y2) の範囲に紙を置くとき、一つ目は (1, 1) - (3, 3) なので、その座標に対応する四角形の隅の四点を次のように±1する。

左上(角の内) + 1
右下(角の外) + 1
左下(辺の外) - 1
右上(辺の外) - 1

すると、

	1	3
0	0	0
1	1	-1
2	0	0
3	-1	1
4	0	0

になる。

続いて二つ目の (2, 2) - (4, 4) も同様に±1すると、

	1	2	3	4
0	0	0	0	0
1	1	0	-1	0
2	0	1	0	-1
3	-1	0	1	0
4	0	-1	0	1

になる。

それを横と

	1	2	3
0	0	0	0
1	1	1	0
2	0	1	1
3	-1	-1	0
4	0	-1	-1

縦に

	1	2	3
0	0	0	0
1	1	1	0
2	1	2	1
3	0	1	1
4	0	0	0

累積和をとる。

最後に 1 以上の値の個数が答え 7 になる。

単純な実装 (TLE)

N = gets.to_i                                       # => 2
R = N.times.collect { gets.split.collect(&:to_i) }  # => [[1, 1, 3, 3], [2, 2, 4, 4]]
counts = {}
R.each do |x1, y1, x2, y2|
  (y1...y2).each do |y|
    (x1...x2).each do |x|
      counts[[x, y]] = true
    end
  end
end
p counts.size                                       # => 7

x2, y2 の座標を含まない点に注意する。

解説の模範解答風の実装 (AC)

N = gets.to_i                                       # => 2
R = N.times.collect { gets.split.collect(&:to_i) }  # => [[1, 1, 3, 3], [2, 2, 4, 4]]
W = R.collect { |x1, y1, x2, y2| x2 }.max.next      # => 5
H = R.collect { |x1, y1, x2, y2| y2 }.max.next      # => 5

S = Array.new(H) { Array.new(W, 0) }
R.each do |x1, y1, x2, y2|
  S[y1][x1] += 1 # 左上(角の内)
  S[y2][x2] += 1 # 右下(角の外)
  S[y2][x1] -= 1 # 左下(辺の外)
  S[y1][x2] -= 1 # 右上(辺の外)
end

H.times do |y, a = 0|
  W.times { |x| S[y][x] = (a += S[y][x]) }
end

W.times do |x, a = 0|
  H.times { |y| S[y][x] = (a += S[y][x]) }
end

p S.sum { |e| e.count(&:positive?) }                # => 7

一行目と左端はパディングではない。