累積和（１次元）③

問題

$D$日間に渡ってあるイベントが開催され、$N(=len(member))$ 人が出席します。

参加者 $ member_i(i=1,2,…,N) $ は $ member_i[‘start’] $ 日目から $ member_i[‘end’] $ 日目まで出席する予定です。

各日のa出席者数を出力してください。

[制約]
🔹$ 1 \leqq D \leqq 100000 $
🔹$ 1 \leqq N(=len(member)) \leqq 100000 $
🔹$ 1 \leqq member[‘start’] \leqq member[‘end’] \leqq D $

解き方・ソースコード

累積和を使ってこの問題を解いていきます。

まず、出席者数の前日比を計算します。

次に前日比の累積和を計算することで、各日の出席者数を求めることができます。

累積和で出席者数が求められる理由は、以下の通りです。

🔹１日目の出席者数は１日目の前日比と一致する。
🔹$d(\geqq 2)$ 日目の出席者数は$d-1$日目の出席者数と $d$ 日目の前日比を足した値と一致する。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#-------- 入力例１ ---------
D = 8        # イベント開催日数
# 参加者ごとの出席期間
member = [
    {'start':2, 'end':3},
    {'start':5, 'end':6},
    {'start':2, 'end':7},
    {'start':3, 'end':5},
    {'start':1, 'end':5}
] 
#---------------------------
# 前日比の算出
B = [0] * (D + 2)
for i, x in enumerate(member):
    B[x['start']] += 1
    B[x['end'] + 1] -= 1

# 累積和を計算
Answer = [ None ] * (D + 2)
Answer[0] = 0
for d in range(1, D + 1):
    Answer[d] = Answer[d - 1] + B[d]

# 出力
for d in range(1, D + 1):
    print('{}日目の参加人数は {}人'.format(d, Answer[d]))

[実行結果（入力例１）]

1日目の参加人数は 1人

2日目の参加人数は 3人

3日目の参加人数は 4人

4日目の参加人数は 3人

5日目の参加人数は 4人

6日目の参加人数は 2人

7日目の参加人数は 1人

8日目の参加人数は 0人

イベントの各日ごとの参加人数をカウントすることができました。