🍡

[鉄則A07] Event Attendance

2024/04/21に公開

Ruby

差分による累積和の基本問題。

問題を要約する

出席者ごとに何日から何日まで出席するかわかっている
各日の出席者数は？

解き方

前日比の配列を元に累積和をとる

前日比は「入った日に +1」「出た日に -1」する。

境界に気をつける

参加しなくなるのは翌日なので3日目までなら4日目に -1 する。それと関係して、イベントが3日目までの場合でも4日目に書き込むので、前日比の配列のサイズは「イベント日数 + 1」にしないといけない。

単純な実装 (TLE)

D = gets.to_i  # => 8
N = gets.to_i  # => 5
LR = N.times.collect { gets.split.collect(&:to_i).collect(&:pred) }
ans = D.times.collect do |day|
  LR.count { |l, r| day.between?(l, r) }
end
ans            # => [1, 2, 4, 3, 4, 3, 2, 0]
puts ans

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

解説の模範解答 (AC)

D = gets.to_i                                           # => 8
N = gets.to_i                                           # => 5
LR = N.times.collect { gets.split.collect(&:to_i).collect(&:pred) }
B = Array.new(D.next, 0)        # 期間 + 1
LR.each do |l, r|
  B[l] += 1
  B[r + 1] -= 1                 # いなくなるのは翌日なので +1
end
B                                                       # => [1, 1, 2, -1, 1, -1, -1, -2, 0]
S = B.each_with_object([0]) { |e, m| m << m.last + e }  # => [0, 1, 2, 4, 3, 4, 3, 2, 0, 0]
ans = S[1..-2]                                          # => [1, 2, 4, 3, 4, 3, 2, 0]
puts ans

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