🍡

[鉄則A10] Resort Hotel

2024/04/29に公開

Ruby

累積 max 問題。

問題を要約する

工事で L から R までの部屋が使えない (日ごとに変わる)
工事期間中でも使える最大の部屋の大きさは？

単純に実装すると遅い理由

2〜4 日目に工事が入るとする。

	0	1	2	3	4	5	6
使える？	○	○	×	×	×	○	○
部屋の大きさ	1	2				3	1

そのとき使える部屋は 0 1 と 5 6 になる。そのあとの部屋たちの大きさ 1 2 と 3 1 からいちばん大きな値を探すのがたいへん。

どうなっていてほしいか

左右のブロックで部屋の大きさの最大値がすぐにわかればいい。

左 0 1 の部屋の大きさ 1 2 の最大は 2
右 5 6 の部屋の大きさ 3 1 の最大は 3

これがすぐに求まれば 2 か 3 の大きい方とするだけになる。だが、どうやって？

累積 max

→ と ← の方向の累積 max を用意する。「和」ではない。

	0	1	2	3	4	5	6
部屋の大きさ	1	2	5	5	2	3	1
→ 方向の累積 max	1	2	5	5	5	5	5
← 方向の累積 max	5	5	5	5	3	3	1

そこで 2〜4 が工事中とすれば、

	0	1	2	3	4	5	6
部屋の大きさ	1	2	5	5	2	3	1
→ 方向の累積 max	1	2	×	×	×	5	5
← 方向の累積 max	5	5	×	×	×	3	1

→ の 1 と → の 5 を見れば不思議なことに 2 と 3 が入っている。

同様に工事中の期間を 3〜5 とすると、

	0	1	2	3	4	5	6
部屋の大きさ	1	2	5	5	2	3	1
→ 方向の累積 max	1	2	5	×	×	×	5
← 方向の累積 max	5	5	5	×	×	×	1

5 と 1 を比べるだけでいいのも表からわかる。

初日や最終日にも工事が入る場合

問題としては初日と最終日は工事が行われないルールになっている。が、もちろん現実の問題解決では考慮する必要がある。

単純な実装 (TLE)

N = gets.to_i                                            # => 7
A = gets.split.collect(&:to_i)                           # => [1, 2, 5, 5, 2, 3, 1]
D = gets.to_i                                            # => 2
LR = D.times.collect { gets.split.collect(&:to_i) }      # => [[3, 5], [4, 6]]
LR = LR.collect { |e| e.collect(&:pred) }                # => [[2, 4], [3, 5]]
ans = LR.collect do |l, r|
  rooms = N.times.reject { |room| room.between?(l, r) }  # => [0, 1, 5, 6], [0, 1, 2, 6]
  rooms.collect { |room| A[room] }.max                   # => 3, 5
end
puts ans

解説の模範解答 (AC)

324 ms

N = gets.to_i                                           # => 7
A = gets.split.collect(&:to_i)                          # => [1, 2, 5, 5, 2, 3, 1]
D = gets.to_i                                           # => 2
LR = D.times.collect { gets.split.collect(&:to_i) }     # => [[3, 5], [4, 6]]
LR = LR.collect { |e| e.collect(&:pred) }               # => [[2, 4], [3, 5]]

# → 方向の累積 max
a = 0
P = A.collect { |e| a = [a, e].max }                    # => [1, 2, 5, 5, 5, 5, 5]

# ← 方向の累積 max
a = 0
Q = A.reverse.collect { |e| a = [a, e].max }.reverse    # => [5, 5, 5, 5, 3, 3, 1]

ans = LR.collect { |l, r| [P[l.pred], Q[r.next]].max }  # => [3, 5]
puts ans