累積和（１次元）③

問題

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

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

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

[制約]
🔹1≦D≦100000
🔹1≦N(=len(member))≦100000
🔹1≦member[‘start′]≦member[‘end′]≦D

解き方・ソースコード

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

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

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

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

🔹１日目の出席者数は１日目の前日比と一致する。
🔹d(≧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人

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