コンテンツにスキップ

yukicoder contest 517 D - Streaming Schedule

サイト
yukicoder
コンテスト
yukicoder contest 517
問題
D - Streaming Schedule

NN 日間、毎日「配信する」か「休む」かを選びます。ii 日目に配信するとファンが AiA_i 人増え、休むと何も起きません(1≤Ai≤1091 \le A_i \le 10^9)。

ただし、BB 日以上続けて休むことはできず、CC 日以上続けて配信することもできません(2≤B,C≤N+12 \le B, C \le N + 1)。増えるファンの人数の最大値を求めてください(N≤3×105N \le 3 \times 10^5)。

配信が続く区間を「配信区間」と呼びます。配信区間の長さは C−1C - 1 以下、休みが続く区間の長さは B−1B - 1 以下でなければなりません。

3 日以上続く休みは考えなくてよい

Section titled “3 日以上続く休みは考えなくてよい”

Ai≥1A_i \ge 1 なので、配信する日は多いほうが得です。3 日以上続く休みがあれば、その真ん中の 1 日を配信に変えられます。この日の両隣は休みのままなので、長さ 1 の配信区間ができるだけです。C≥2C \ge 2 なので長さ 1 の配信区間は必ず許され、休みの区間も短くなるだけなので、条件は崩れません。しかもファンは増えます。

したがって、最適解では休みは 2 日までしか続きません。B=2B = 2 なら連続休みは 1 日まで、B≥3B \ge 3 なら 2 日まで許されます。以下では、B≥3B \ge 3 のときは連続休みの長さに上限を設けずに計算します。上限を超える休み方は、真ん中を配信に変えたものより必ず悪いので、最大値は変わりません。

resti\mathrm{rest}_i を「ii 日目に休むときの、ii 日目までのファンの増加数の最大値」とします。ii 日目に休む直前の状況で場合分けします。

  • 前日も休み:resti−1\mathrm{rest}_{i-1}。B≥3B \ge 3 のときだけ選べます。
  • 前日まで配信区間:配信区間が jj 日目から i−1i - 1 日目までなら、j−1j - 1 日目は休みです。値は restj−1+(Aj+⋯+Ai−1)\mathrm{rest}_{j-1} + (A_j + \dots + A_{i-1}) で、配信区間の長さの制約から i−(C−1)≤j≤i−1i - (C - 1) \le j \le i - 1 です。
  • ii 日目が 1 日目:何もしていないので 00 です。

1 日目より前の日を「0 日目に休んだ」とみなして rest0=0\mathrm{rest}_0 = 0 とおくと、配信区間が 1 日目から始まる場合も 2 つ目の式で扱えます。ただし、1 日目に休むときに「前日も休み」の場合として扱うと、B=2B = 2 では選べなくなってしまいます。そこで 1 日目に休む場合は、BB によらず 00 とします(下の補足も参照)。

最終日に休む場合の答えは restN\mathrm{rest}_N、最終日まで配信する場合の答えは jj 日目から NN 日目までの配信区間を使った同じ式で求まります。

累積和 Si=A1+⋯+AiS_i = A_1 + \dots + A_i を使うと、2 つ目の式は

restj−1+Si−1−Sj−1=(restj−1−Sj−1)+Si−1\mathrm{rest}_{j-1} + S_{i-1} - S_{j-1} = (\mathrm{rest}_{j-1} - S_{j-1}) + S_{i-1}

と書けます。ii が 1 増えると、jj の範囲は 1 つずつ右にずれます。したがって、長さ C−1C - 1 の窓の中での restj−1−Sj−1\mathrm{rest}_{j-1} - S_{j-1} の最大値が分かればよく、これは deque を使ったスライド最大値で求まります。

計算量は O(N)O(N) です。

最初は 1 日目に休む場合も「前日も休み」として扱っていて、WA になりました。たとえば N=2,B=2,C=2,A=(8,9)N = 2, B = 2, C = 2, A = (8, 9) では、1 日目に休んで 2 日目に配信する 99 が正解です。しかし、1 日目の休みを「0 日目からの連続休み」とみなすと、B=2B = 2 で禁止されて 88 になってしまいます。0 日目は実際には休みではないので、1 日目だけは BB によらず休めるようにする必要があります。

Python
from collections import deque
N, B, C = map(int, input().split())
A = list(map(int, input().split()))
t = 0
k = 0
d = deque()
e = deque()
for i, a in enumerate(A):
if d:
u = e[0] + k
else:
u = -(10**18)
if B > 2 or i == 0:
u = max(u, t)
d.append(t - k)
e.append(t - k)
while len(e) >= 2 and e[-2] < e[-1]:
x = e.pop()
e.pop()
e.append(x)
k += a
while len(d) >= C:
x = d.popleft()
if len(e) > 0 and e[0] == x:
e.popleft()
t = u
print(max(t, max(d) + k))

変数の意味は次のとおりです。

  • t:前日に休んだときの最大値(resti−1\mathrm{rest}_{i-1})
  • k:前日までの累積和(Si−1S_{i-1})
  • u:その日に休んだときの最大値(resti\mathrm{rest}_i)
  • d:配信区間の始まりの候補 jj について、restj−1−Sj−1\mathrm{rest}_{j-1} - S_{j-1} を並べた窓。最大 C−1C - 1 個を持ちます。
  • e:d のうち、後ろにより大きい値がないものだけを残した deque。先頭が窓の中の最大値です。

d から要素を捨てるときは、その値が e の先頭と等しければ e からも捨てます。値しか比べていませんが、別の要素を取り違えることはありません。捨てる要素 xx が e から消えているなら、xx より後に xx より大きい値が窓の中にあります。そのため e の先頭(窓の最大値)は xx より大きく、等しくはなりません。最後の max(d) + k は、最終日まで配信する場合の値です。