🍡
[鉄則A09] Winter in ALGO Kingdom
差分+二次元の累積和問題。
問題を要約する
- 矩形範囲に雪が降る
- 日ごとの範囲データがある
- 最後に積雪状態はどうなっている?
解き方
- 矩形の隅の四点を±1する
- それを矩形の個数分繰り返す
- 最後にまとめて1回だけ累積和テーブルを作る
例1でシミュレーション
5 x 5 のマップ内の (x1, y1) - (x2, y2)
の範囲に雪が降るとしたとき、一つ目は (0, 0) - (2, 2)
なので、矩形の隅の四点±1する。
- 左上(角の内) + 1
- 右下(角の外) + 1
- 左下(辺の外) - 1
- 右上(辺の外) - 1
すると、
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | -1 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | -1 | 0 | 0 | 1 | 0 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 0 |
になる。
このとき、仮に (x2, x2) が (4, 4)
だとすれば右下(角の外)が W x H を超えるので右と下にパディングが必要になる。これをせずにかなりはまった。ここでは一長一短あるものの範囲チェックして W x H を超えないようにする方法もある。
続いて二つ目の (1, 1) - (3, 3)
も±1すると、
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | -1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | -1 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | -1 | 0 | 0 | 1 | 0 | 0 |
4 | 0 | -1 | 0 | 0 | 1 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 0 |
になる。
それを→↓の順で累積和にする。
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 | 0 |
2 | 0 | 1 | 2 | 2 | 1 | 0 |
3 | 0 | 1 | 2 | 2 | 1 | 0 |
4 | 0 | 0 | 1 | 1 | 1 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 0 |
それの一行目と左端の列を外したのが答えになる。
1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|
1 | 1 | 1 | 1 | 0 | 0 |
2 | 1 | 2 | 2 | 1 | 0 |
3 | 1 | 2 | 2 | 1 | 0 |
4 | 0 | 1 | 1 | 1 | 0 |
5 | 0 | 0 | 0 | 0 | 0 |
あとで気づいたが、最後に範囲の合計を出せとは言われていないため、累積和テーブルの一行目と左端の一列はなくてもいい。いや、むしろない方が実装が楽になる。
単純な実装 (TLE)
H, W, N = gets.split.collect(&:to_i) # => [5, 5, 2]
R = N.times.collect { gets.split.collect(&:to_i) } # => [[1, 1, 3, 3], [2, 2, 4, 4]]
R = R.collect { |e| e.collect(&:pred) } # => [[0, 0, 2, 2], [1, 1, 3, 3]]
S = Array.new(W) { Array.new(H, 0) }
R.each do |y1, x1, y2, x2|
(x1..x2).each do |x|
(y1..y2).each do |y|
S[x][y] += 1
end
end
end
S # => [[1, 1, 1, 0, 0], [1, 2, 2, 1, 0], [1, 2, 2, 1, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0]]
puts H.times.collect { |y| W.times.collect { |x| S[y][x] } * " " }
わかりやすいが最悪 O(NWH) かかるので TLE になる。
解説の模範解答風 (AC)
1140 ms
H, W, N = gets.split.collect(&:to_i) # => [5, 5, 2]
R = N.times.collect { gets.split.collect(&:to_i) } # => [[1, 1, 3, 3], [2, 2, 4, 4]]
# 必ず 0-based で統一する
R = R.collect { |e| e.collect(&:pred) } # => [[0, 0, 2, 2], [1, 1, 3, 3]]
# 範囲に対応する四角形の隅の四点を±1する
F = Array.new(H.next) { Array.new(W.next, 0) }
R.each do |y1, x1, y2, x2|
F[y1 + 0][x1 + 0] += 1 # 左上(角の内)
F[y2 + 1][x2 + 1] += 1 # 右下(角の外)
F[y2 + 1][x1 + 0] -= 1 # 左下(辺の外)
F[y1 + 0][x2 + 1] -= 1 # 右上(辺の外)
end
# 上と左に一行一列入れる
S = Array.new(H.next) { Array.new(W.next, 0) }
# 横方向の累積和 (S[v] = 前 + F)
(1..H).each do |y|
(1..W).each do |x|
S[y][x] = S[y][x.pred] + F[y.pred][x.pred]
end
end
# 横方向の累積和 (S[v] += 上)
(1..W).each do |x|
(1..H).each do |y|
S[y][x] += S[y.pred][x]
end
end
puts (1..H).collect { |y| (1..W).collect { |x| S[y][x] } * " " }
リファクタリング後 (AC)
こちらの実装が参考になった。
- 二次元配列は2つもいらない
- 累積和テーブルの一行目と左端の一列はいらない
- 累積和は前の値を保持する変数を持っておけばよい
ということで、それを踏まえて改善したもの。
1098 ms
H, W, N = gets.split.collect(&:to_i) # => [5, 5, 2]
R = N.times.collect { gets.split.collect(&:to_i) } # => [[1, 1, 3, 3], [2, 2, 4, 4]]
R = R.collect { |e| e.collect(&:pred) } # => [[0, 0, 2, 2], [1, 1, 3, 3]]
S = Array.new(H.next) { Array.new(W.next, 0) }
R.each do |y1, x1, y2, x2|
S[y1 + 0][x1 + 0] += 1 # 左上(角の内)
S[y2 + 1][x2 + 1] += 1 # 右下(角の外)
S[y2 + 1][x1 + 0] -= 1 # 左下(辺の外)
S[y1 + 0][x2 + 1] -= 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
puts H.times.collect { |y| W.times.collect { |x| S[y][x] } * " " }
Discussion