[鉄則B07] Convenience Store 2

https://atcoder.jp/contests/tessoku-book/tasks/math_and_algorithm_al

差分による累積和の応用問題。

問題を要約する

• 従業員は L 時に出勤して R 時に退勤する
• 各時の従業員数は？

ひっかけポイント

• R 時には退勤している

前問の「L 日目から R 日目まで」の言い回しに釣られてはいけない。R 時には退勤しているので R 時に -1 する。

単純な実装 (TLE)

T = gets.to_i                                        # => 10
N = gets.to_i                                        # => 7
LR = N.times.collect { gets.split.collect(&:to_i) }  # => [[0, 3], [2, 4], [1, 3], [0, 3], [5, 6], [5, 6], [5, 6]]
ans = T.times.collect do |e|
  LR.count { |l, r| e.between?(l, r - 1) }
end
ans                                                  # => [2, 3, 4, 1, 0, 3, 0, 0, 0, 0]
puts ans

累積和が正しいかを確認するためにこちらの方法でも答えを出しておく。

解説の模範解答 (AC)

T = gets.to_i                                           # => 10
N = gets.to_i                                           # => 7
LR = N.times.collect { gets.split.collect(&:to_i) }     # => [[0, 3], [2, 4], [1, 3], [0, 3], [5, 6], [5, 6], [5, 6]]
B = Array.new(T.next, 0)
LR.each do |l, r|
  B[l] += 1
  B[r] -= 1                     # r の時点ですでに退勤している
end
B                                                       # => [2, 1, 1, -3, -1, 3, -3, 0, 0, 0, 0]
S = B.each_with_object([0]) { |e, m| m << m.last + e }  # => [0, 2, 3, 4, 1, 0, 3, 0, 0, 0, 0, 0]
ans = S[1..-2]                                          # => [2, 3, 4, 1, 0, 3, 0, 0, 0, 0]
puts ans

累積和配列の先頭と最後の要素は省く。