概要

この問題は、\(N\) 日間のシフトの中で「連続勤務は \(K-1\) 日まで」「連続休暇は \(M-1\) 日まで」という制約を守りつつ、得られる給料の合計を最大化する問題です。

動的計画法（DP）をベースに、スライディングウィンドウ最大値を効率的に求める手法（デック）を組み合わせることで、膨大な選択肢の中から最適なスケジュールを高速に導き出します。

考察

1. 状態の定義

各日程において「働く」か「休む」かの選択が必要ですが、制約（連続日数）があるため、「最後にいつ休んだか」や「最後にいつ働いたか」が重要になります。そこで、以下の2つのDPテーブルを定義します。

• \(dp\_work[i]\) : \(i\) 日目にシフトに入った場合の、\(i\) 日目までの給料の最大合計
• \(dp\_rest[i]\) : \(i\) 日目に休みを入れた場合の、\(i\) 日目までの給料の最大合計

2. 遷移の考え方

• \(dp\_work[i]\) の計算: \(i\) 日目に働くためには、その直前の休みが \(j\) 日目である必要があります。連続勤務制限（\(K\) 日以上連続不可）より、\(i - j < K\) 、すなわち \(j \geq i - K + 1\) を満たす必要があります。 \(j\) 日目に休んでから \(j+1\) 日目〜 \(i\) 日目まで連続して働く場合の給料は、累積和 \(S\) を用いて \((S[i] - S[j])\) と表せます。 $\(dp\_work[i] = \max_{i-K+1 \le j \le i-1} \{ dp\_rest[j] + S[i] - S[j] \}\)\( これを変形すると、\)\max { dp_rest[j] - S[j] } + S[i]$ となり、区間内の最大値を求める問題に帰着します。

• \(dp\_rest[i]\) の計算: \(i\) 日目に休むためには、その直前の勤務が \(j\) 日目である必要があります。連続休暇制限（\(M\) 日以上連続不可）より、\(j \geq i - M + 1\) を満たす必要があります。 $\(dp\_rest[i] = \max_{i-M+1 \le j \le i-1} \{ dp\_work[j] \}\)\( （ただし、1日目から \)i\( 日目まで一度も働かずに休み続ける場合は、 \)i < M\( のときのみ \)0$ 円として考慮します）

3. 高速化の必要性

素朴に各 \(i\) に対して \(j\) を全探索すると、全体で \(O(NK)\) または \(O(NM)\) の時間がかかり、制約（\(N=2 \times 10^5\)）では間に合いません。 しかし、遷移式を見ると「特定の区間内での最大値」を求めているだけなので、スライディングウィンドウ最大値のアルゴリズム（両端キュー/デックを使用）を用いることで、各遷移を \(O(1)\) で行うことができます。

アルゴリズム

1. 累積和の準備: 給料 \(A\) の累積和 \(S\) を計算し、任意の区間の給料合計を \(O(1)\) で出せるようにします。
2. デックの初期化:
   • dq_rest_S: \((dp\_rest[j] - S[j])\) の値を管理するデック。
   • dq_work: \(dp\_work[j]\) の値を管理するデック。
3. DPの実行: \(i = 1\) から \(N\) まで以下を繰り返します。
   • デックの先頭を見て、範囲外（\(i-K+1\) 未満や \(i-M+1\) 未満）になった古いインデックスを削除します。
   • デックの先頭にある最大値を使って \(dp\_work[i]\) と \(dp\_rest[i]\) を更新します。
   • 新しく求まった値をデックに追加します。この際、自分より小さい値がデックの末尾にあれば、それらは今後最大値になることはないので削除します。
4. 結果の出力: \(\max(dp\_work[N], dp\_rest[N])\) が答えです。

計算量

• 時間計算量: \(O(N)\)
  • 各要素はデックに高々1回追加され、1回削除されるため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • DPテーブル、累積和、デックの保持に \(O(N)\) のメモリを使用します。

実装のポイント

• 初期状態: 0日目は「休み」の状態（\(dp\_rest[0] = 0\)）からスタートし、これをデックに入れておくことで、1日目からの勤務を正しく計算できます。

• 負の無限大: 到達不可能な状態を扱うため、非常に小さな値（\(-10^{18}\) など）で初期化しますが、この問題の制約（\(K, M \ge 2\)）では、常に何らかのシフトの組み方が存在します。

• 累積和の活用: dp_work[i] の計算時に \(S[i]\) を分離して考えることで、デックに入れる値を \(dp\_rest[j] - S[j]\) という単一の項にまとめられるのがポイントです。

  ソースコード

import sys
import collections

# 競技プログラミングのエキスパートとして、与えられた制約と条件を効率的に処理するコードを実装します。
# 連続勤務日数 K 未満、連続休日数 M 未満という条件を動的計画法（DP）とスライディングウィンドウ最大値（デック）を用いて
# O(N) の時間計算量で解きます。

def solve():
    # 標準入力から全データを読み込み、高速に処理します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    A = list(map(int, input_data[3:]))

    # 給料の累積和を計算します。
    # S[i] は 1 日目から i 日目までの給料の合計を表します。
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + A[i]

    # dp_work[i]: i 日目にシフトに入った場合の、i 日目までの給料の最大合計
    # dp_rest[i]: i 日目に休みを入れた場合の、i 日目までの給料の最大合計
    INF = 10**18
    dp_work = [-INF] * (N + 1)
    dp_rest = [-INF] * (N + 1)

    # 0 日目は便宜上「休み」の状態からスタートすると考えます。
    dp_rest[0] = 0
    
    # スライディングウィンドウ最大値を効率的に求めるためのデックを用意します。
    # dq_rest_S は (dp_rest[j] - S[j]) を最大化するインデックス j を保持します。
    dq_rest_S = collections.deque([0])
    # dq_work は dp_work[j] を最大化するインデックス j を保持します。
    dq_work = collections.deque()

    for i in range(1, N + 1):
        # 1. i 日目に働く場合 (dp_work[i] の計算)
        # 直近の休みを j 日目 (max(0, i-K+1) <= j <= i-1) とすると、
        # j+1 日目から i 日目まで連続して働くことになります。
        # その時の給料合計は (S[i] - S[j]) + dp_rest[j] です。
        while dq_rest_S and dq_rest_S[0] < i - K + 1:
            dq_rest_S.popleft()
        
        if dq_rest_S:
            best_j = dq_rest_S[0]
            dp_work[i] = S[i] - S[best_j] + dp_rest[best_j]
        
        # 2. i 日目に休む場合 (dp_rest[i] の計算)
        # 直近の勤務を j 日目 (max(1, i-M+1) <= j <= i-1) とすると、
        # j+1 日目から i 日目まで連続して休むことになります。
        # また、1 日目から i 日目まで全て休む場合は i < M の時のみ可能です。
        while dq_work and dq_work[0] < i - M + 1:
            dq_work.popleft()
        
        res = -INF
        if i < M:
            res = 0 # 全て休む場合
        if dq_work:
            if dp_work[dq_work[0]] > res:
                res = dp_work[dq_work[0]]
        dp_rest[i] = res

        # 3. 次の日以降の計算のためにデックを更新します。
        # dq_work の更新
        if dp_work[i] > -INF:
            while dq_work and dp_work[dq_work[-1]] <= dp_work[i]:
                dq_work.pop()
            dq_work.append(i)
        
        # dq_rest_S の更新
        if dp_rest[i] > -INF:
            val = dp_rest[i] - S[i]
            while dq_rest_S and (dp_rest[dq_rest_S[-1]] - S[dq_rest_S[-1]]) <= val:
                dq_rest_S.pop()
            dq_rest_S.append(i)

    # N 日間のシフトが終わった時点で、最後の状態が「勤務」か「休み」かの最大値を取ります。
    # 条件を満たす組み方が存在しない場合は -1 を出力しますが、K, M >= 2 の制約下では常に存在します。
    ans = max(dp_work[N], dp_rest[N])
    if ans < 0:
        print("-1")
    else:
        print(ans)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。