概要

\(N\) 日間のシフトにおいて、連続勤務日数を \(K-1\) 日以下、連続休日数を \(M-1\) 日以下に抑えつつ、給料の合計を最大化する問題です。DPとスライディングウィンドウ最大値を組み合わせて \(O(N)\) で解きます。

考察

重要な気づき

各日は「働く」か「休む」かの2択です。制約は以下の2つです：

• 連続して \(K\) 日以上働いてはいけない（連続勤務は最大 \(K-1\) 日）
• 連続して \(M\) 日以上休んではいけない（連続休日は最大 \(M-1\) 日）

DP の状態設計

日 \(i\) まで決めたときの最大給料を、最終日が勤務か休みかで分けて管理します。

• \(\text{dp\_work}[i]\)：日 \(1\) ～ \(i\) のシフトを決め、日 \(i\) に働くときの最大給料
• \(\text{dp\_rest}[i]\)：日 \(1\) ～ \(i\) のシフトを決め、日 \(i\) に休むときの最大給料

遷移の導出

dp_work[i] の遷移： 日 \(i\) に働く場合、直前の連続勤務の開始地点を考えます。連続勤務が最大 \(K-1\) 日なので、最後に休んだ日 \(j\) は \(j \geq i - K + 1\) を満たす必要があります。日 \(j\) が最後の休日なら、日 \(j+1\) ～ \(i\) はすべて勤務で、その給料は \(\text{prefix}[i] - \text{prefix}[j]\) です。

\[\text{dp\_work}[i] = \max_{j \in [\max(0,\, i-K+1),\, i-1]} \left( \text{dp\_rest}[j] + \text{prefix}[i] - \text{prefix}[j] \right)\]

これを変形すると：

\[\text{dp\_work}[i] = \text{prefix}[i] + \max_{j \in [\max(0,\, i-K+1),\, i-1]} \left( \text{dp\_rest}[j] - \text{prefix}[j] \right)\]

dp_rest[i] の遷移： 日 \(i\) に休む場合、最後に働いた日 \(j\) は \(j \geq i - M + 1\) を満たす必要があります。日 \(j+1\) ～ \(i\) はすべて休みなので給料は増えません。

\[\text{dp\_rest}[i] = \max_{j \in [\max(0,\, i-M+1),\, i-1]} \text{val\_for\_rest}[j]\]

ここで \(\text{val\_for\_rest}[j] = \text{dp\_work}[j]\)（\(j \geq 1\)）、\(\text{val\_for\_rest}[0] = 0\)（最初からずっと休む場合）です。

素朴な方法の問題点

各 \(i\) に対して窓内の最大値を愚直に求めると \(O(NK)\) や \(O(NM)\) となり、\(N\) が最大 \(2 \times 10^5\) では TLE の恐れがあります。

解決策：スライディングウィンドウ最大値

単調キュー（deque） を使えば、スライディングウィンドウ内の最大値を各ステップ \(O(1)\)（ならし）で求められます。

アルゴリズム

1. 累積和 \(\text{prefix}[i]\) を計算する。
2. 初期値：\(\text{dp\_rest}[0] = 0\)（0日間で休み状態）、\(\text{dp\_work}[0] = -\infty\)。
3. 2つの単調キューを用意する：
   • dq_work：\(\text{dp\_rest}[j] - \text{prefix}[j]\) のスライディングウィンドウ最大値（窓幅 \(K\)）
   • dq_rest：\(\text{val\_for\_rest}[j]\) のスライディングウィンドウ最大値（窓幅 \(M\)）
4. \(i = 1, 2, \ldots, N\) の順に：
   • dq_work から窓外の要素を除去し、\(\text{dp\_work}[i] = \text{prefix}[i] +\) キュー先頭の値
   • dq_rest から窓外の要素を除去し、\(\text{dp\_rest}[i] =\) キュー先頭の値
   • 新しい値を各キューに追加（末尾から不要な要素を除去して単調性を保つ）
5. 答えは \(\max(\text{dp\_work}[N],\, \text{dp\_rest}[N])\)。\(-\infty\) なら -1 を出力。

具体例

\(N=5,\, K=3,\, M=2,\, A=[3, 1, 4, 1, 5]\) の場合：

• 連続勤務は最大2日、連続休日は最大1日
• 例えば「働・働・休・働・働」→ \(3+1+0+1+5=10\)
• 「働・休・働・働・休」→ \(3+0+4+1+0=8\)

最適解は条件を満たす組み合わせの中で最大のものです。

計算量

• 時間計算量: \(O(N)\)（各要素はキューに最大1回追加・1回削除）
• 空間計算量: \(O(N)\)（DP配列・累積和・キュー）

実装のポイント

• 基底ケースの扱い：\(j=0\) は「まだ1日も確定していない」状態を表す。\(\text{dp\_rest}[0]=0\)（全休み開始）、\(\text{dp\_work}[0]=-\infty\)（0日目に働くことは不可能）。\(\text{val\_for\_rest}[0]=0\) とすることで、最初から休み続ける場合を正しく扱う。

• 遷移の変形：\(\text{dp\_work}\) の遷移では \(\text{dp\_rest}[j] - \text{prefix}[j]\) をまとめることで、\(\text{prefix}[i]\) を窓の外に出せる。これにより単調キューが適用可能になる。

• 不可能判定：\(K=1\)（1日も働けない）かつ \(M=1\)（1日も休めない）のような場合、\(N \geq 1\) なら解が存在しない。最終的な答えが \(-\infty\) のままなら -1 を出力する。

  ソースコード

import sys
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    # State: dp[i][0] = max salary considering days 0..i-1, where day i-1 is a rest day
    #        dp[i][1] = max salary considering days 0..i-1, where day i-1 is a work day
    # 
    # Actually, let's think more carefully with DP.
    # 
    # Let dp[i] = maximum salary for the first i days, where the i-th day's status is determined.
    # We need to track consecutive work/rest days which makes this complex.
    #
    # Alternative approach:
    # dp_work[i] = max total salary for days 1..i where day i is a work day
    # dp_rest[i] = max total salary for days 1..i where day i is a rest day
    #
    # For dp_work[i]: day i is worked. Before day i, there could be 0..K-2 consecutive work days.
    #   So the last rest day before this work streak was at some day j where i - j <= K-1, i.e., j >= i-K+1
    #   dp_work[i] = max over j in [max(0, i-K+1)..i-1] of dp_rest[j] + sum(A[j+1..i])
    #   Also j=0 means all days 1..i are worked (if i <= K-1).
    #
    # For dp_rest[i]: day i is rest. Before day i, there could be 0..M-2 consecutive rest days.
    #   So the last work day before this rest streak was at some day j where i - j <= M-1, i.e., j >= i-M+1
    #   dp_rest[i] = max over j in [max(0, i-M+1)..i-1] of dp_work[j]
    #   Also j=0 means all days 1..i are rest (if i <= M-1).
    
    # prefix sum for A (1-indexed: prefix[i] = A[0]+...+A[i-1])
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    NEG_INF = float('-inf')
    
    # dp_work[i]: max salary for days 1..i, day i is work. i from 1..N
    # dp_rest[i]: max salary for days 1..i, day i is rest. i from 1..N
    # We also define dp_work[0] = NEG_INF (no day 0 to work), dp_rest[0] = 0 (base: no days, trivially rest)
    
    dp_work = [NEG_INF] * (N + 1)
    dp_rest = [NEG_INF] * (N + 1)
    dp_rest[0] = 0
    
    # dp_work[i] = max over j in [max(0, i-K+1)..i-1] of (dp_rest[j] - prefix[j]) + prefix[i]
    # So we need max of (dp_rest[j] - prefix[j]) over sliding window of size K for j.
    
    # dp_rest[i] = max over j in [max(0, i-M+1)..i-1] of dp_work[j]
    # But also j=0 is allowed if i <= M-1: dp_rest[0] = 0.
    # Sliding window of size M for dp_work[j], but also including j=0 via dp_rest[0].
    # Actually dp_rest[i] = max over j in [max(0,i-M+1)..i-1] of dp_work[j], plus j=0 gives 0 if 0 >= i-M+1.
    # We handle j=0 separately since dp_work[0] = NEG_INF. Let's instead:
    # For dp_rest: we want max of dp_work[j] for j in [max(0,i-M+1)..i-1], but also if i <= M-1, we can have all rest -> 0.
    # Let's define val_rest[j] = dp_work[j] for j>=1, val_rest[0] = 0. Then dp_rest[i] = max of val_rest[j] for j in window.
    
    val_for_work = [NEG_INF] * (N + 1)  # dp_rest[j] - prefix[j]
    val_for_work[0] = dp_rest[0] - prefix[0]  # = 0
    
    val_for_rest = [NEG_INF] * (N + 1)  # dp_work[j] for j>=1, 0 for j=0
    val_for_rest[0] = 0
    
    # Sliding window max using deque
    dq_work = deque()  # for computing dp_work, window over val_for_work
    dq_work.append(0)
    
    dq_rest = deque()  # for computing dp_rest, window over val_for_rest
    dq_rest.append(0)
    
    for i in range(1, N + 1):
        # dp_work[i]: window [max(0, i-K+1)..i-1] over val_for_work
        while dq_work and dq_work[0] < i - K + 1:
            dq_work.popleft()
        if dq_work:
            dp_work[i] = val_for_work[dq_work[0]] + prefix[i]
        
        # dp_rest[i]: window [max(0, i-M+1)..i-1] over val_for_rest
        while dq_rest and dq_rest[0] < i - M + 1:
            dq_rest.popleft()
        if dq_rest:
            dp_rest[i] = val_for_rest[dq_rest[0]]
        
        # Update val_for_work[i] and add to dq_work
        val_for_work[i] = dp_rest[i] - prefix[i]
        while dq_work and val_for_work[dq_work[-1]] <= val_for_work[i]:
            dq_work.pop()
        dq_work.append(i)
        
        # Update val_for_rest[i] and add to dq_rest
        val_for_rest[i] = dp_work[i]
        while dq_rest and val_for_rest[dq_rest[-1]] <= val_for_rest[i]:
            dq_rest.pop()
        dq_rest.append(i)
    
    ans = max(dp_work[N], dp_rest[N])
    
    # Also need to consider ending with rest: last work day j, then rest days j+1..N, need N-j <= M-1
    # This is already handled by dp_rest[N].
    
    if ans == NEG_INF:
        print(-1)
    else:
        print(ans)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。