Atcoder 備忘録_一次元の累積和_問題B07

概要

• 競技プログラミングを始めてみた。
  せっかくなので１テーマごとに解法と学びをアウトプットしてみる。

取り組む内容

• 鉄則本[https://atcoder.jp/contests/tessoku-book] に沿って実施する。
• 
• 言語は Python
• 今回テーマは「一次元の累積和」

問題文

あるコンビニは時刻0に開店し、時刻Tに閉店します。このコンビニにはN人の従業員が働いており、i番目(1≤i≤N)の従業員は時刻Liに出勤し時刻Riに退勤します。

t=0,1,2,…,T−1それぞれについて、時刻t+0.5にコンビニにいる従業員の数を出力するプログラムを作成してください。

制約

• 1≤T≤500000
• 1≤N≤500000
• 0≤Li<Ri≤T(1≤i≤N)入力はすべて整数

出力

全体でT行出力してください。
t+1 行目(0≤t≤T−1)には、時刻t+0.5 にコンビニにいる従業員の数を出力してください。

解法

T = int(input())
N = int(input())

x = [0] * (T+1)

for n in range(N):
  Li, Ri = map(int, input().split())

  x[Li] += 1
  x[Ri] -= 1
  
for i in range(1, T+1):
  x[i] += x[i-1]

for answer in x[:-1]:
  print(answer)

結果

• AC
• Runtime： 912 ms
• メモリ：32568 KB

振り返り

思想

• 出勤時間に+1, 退勤時間に-1をそれぞれ立てる
• その後、一次元累積和を計算すると時間ごとの在籍人数となる

学び

• リストを累積和するのは以下が便利

for i in range(1, T+1):　# +1するかは問題による
  x[i] += x[i-1]

感想

• ↑の累積和リスト作成は汎用性高いので覚えておきたい