AtCoder Beginner Contest 183 D問題

AtCoder Python

前書き

atcoder.jp

D問題

難易度：茶色
時間：60分超

超苦戦して、時間を浪費しましたが、何とか自力で解きました。
キーワードは「累積和」です。

qiita.com

与えられている条件設定は以下の通り。

1≤N≤2*10**5
0≤Si≤Ti≤2*10**5
1≤W,Pi≤10**9

こちらをざっと見てO(N**2)の計算はできないなと察したのですが、二重ループを必要とするアルゴリズムしか最初思い浮かびませんでした。
Ni氏が湯を使用し始めた時間をSi、使用を終えた時間をTi、使用量をPiとします。

  • 配列の区間（Si〜Ti）に使用量Piの値を代入処理（O(N)） * N人分の処理（O(N)）

でO(N**2)になるなとずっと悩んでいました。

回答

import numpy as np
N,M = map(int, input().split())
Tmax, STPlis = 0, []
 
for p in range(N):
  STP = list(map(int, input().split()))
  STPlis.append(STP)
  Tmax = max(STP[1], Tmax)
 
Timelis = np.zeros(Tmax+1)
Sumlis = np.zeros(Tmax+2)
 
for stp in STPlis:
  Timelis[stp[0]] += stp[2]
  Timelis[stp[1]] -= stp[2]
 
for j in range(1,Tmax+1):
  Sumlis[j] = Timelis[j-1]+Sumlis[j-1]
 
if int(max(Sumlis))<=M: print('Yes')
else: print('No')

解説

考えを変えて「累積和」を意識します。

「使用開始時間SI」・「使用終了時間Ti」にのみ使用量Piを配列に当てはめます。
Timelisは「新たに時間tから変化する使用湯量」の配列です。
力学で例えるとこれは「加速度」の配列です。

for stp in STPlis:
  Timelis[stp[0]] += stp[2]
  Timelis[stp[1]] -= stp[2]

Si < t < Tiの継続使用期間では等速直線運動をしているイメージです。
なので 「v = v0 + at」の式で習ったように、「現在tの使用湯量 = (t-1)での使用湯量 + 新たに時間tから変化する使用湯量」になります。
Sumlisは「現在tの使用湯量」の配列で、力学で例えると「速度」の配列です。

for j in range(1,Tmax+1):
  Sumlis[j] = Timelis[j-1]+Sumlis[j-1]

Sumlisの配列から最大値がMを超えていないか確認するだけです。

結果

ACでした。