yukicoder contest 517 D - Streaming Schedule
- サイト
- yukicoder
- コンテスト
- yukicoder contest 517
- 問題
- D - Streaming Schedule
日間、毎日「配信する」か「休む」かを選びます。 日目に配信するとファンが 人増え、休むと何も起きません()。
ただし、 日以上続けて休むことはできず、 日以上続けて配信することもできません()。増えるファンの人数の最大値を求めてください()。
配信が続く区間を「配信区間」と呼びます。配信区間の長さは 以下、休みが続く区間の長さは 以下でなければなりません。
3 日以上続く休みは考えなくてよい
Section titled “3 日以上続く休みは考えなくてよい”なので、配信する日は多いほうが得です。3 日以上続く休みがあれば、その真ん中の 1 日を配信に変えられます。この日の両隣は休みのままなので、長さ 1 の配信区間ができるだけです。 なので長さ 1 の配信区間は必ず許され、休みの区間も短くなるだけなので、条件は崩れません。しかもファンは増えます。
したがって、最適解では休みは 2 日までしか続きません。 なら連続休みは 1 日まで、 なら 2 日まで許されます。以下では、 のときは連続休みの長さに上限を設けずに計算します。上限を超える休み方は、真ん中を配信に変えたものより必ず悪いので、最大値は変わりません。
「休む日」で DP する
Section titled “「休む日」で DP する”を「 日目に休むときの、 日目までのファンの増加数の最大値」とします。 日目に休む直前の状況で場合分けします。
- 前日も休み:。 のときだけ選べます。
- 前日まで配信区間:配信区間が 日目から 日目までなら、 日目は休みです。値は で、配信区間の長さの制約から です。
- 日目が 1 日目:何もしていないので です。
1 日目より前の日を「0 日目に休んだ」とみなして とおくと、配信区間が 1 日目から始まる場合も 2 つ目の式で扱えます。ただし、1 日目に休むときに「前日も休み」の場合として扱うと、 では選べなくなってしまいます。そこで 1 日目に休む場合は、 によらず とします(下の補足も参照)。
最終日に休む場合の答えは 、最終日まで配信する場合の答えは 日目から 日目までの配信区間を使った同じ式で求まります。
スライド最大値で高速化する
Section titled “スライド最大値で高速化する”累積和 を使うと、2 つ目の式は
と書けます。 が 1 増えると、 の範囲は 1 つずつ右にずれます。したがって、長さ の窓の中での の最大値が分かればよく、これは deque を使ったスライド最大値で求まります。
計算量は です。
補足:1 日目に休む場合
Section titled “補足:1 日目に休む場合”最初は 1 日目に休む場合も「前日も休み」として扱っていて、WA になりました。たとえば では、1 日目に休んで 2 日目に配信する が正解です。しかし、1 日目の休みを「0 日目からの連続休み」とみなすと、 で禁止されて になってしまいます。0 日目は実際には休みではないので、1 日目だけは によらず休めるようにする必要があります。
Python
from collections import deque
N, B, C = map(int, input().split())A = list(map(int, input().split()))t = 0k = 0d = 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 = uprint(max(t, max(d) + k))変数の意味は次のとおりです。
t:前日に休んだときの最大値()k:前日までの累積和()u:その日に休んだときの最大値()d:配信区間の始まりの候補 について、 を並べた窓。最大 個を持ちます。e:dのうち、後ろにより大きい値がないものだけを残した deque。先頭が窓の中の最大値です。
d から要素を捨てるときは、その値が e の先頭と等しければ e からも捨てます。値しか比べていませんが、別の要素を取り違えることはありません。捨てる要素 が e から消えているなら、 より後に より大きい値が窓の中にあります。そのため e の先頭(窓の最大値)は より大きく、等しくはなりません。最後の max(d) + k は、最終日まで配信する場合の値です。