概要

\(N\) 個の仕事から 1 つ以上を選び、報酬の合計から「連続して選んだペアの数 \(\times K\)」を引いた利益を最大化する問題です。

考察

各仕事 \(i\) について「選ぶ」か「選ばない」かを決める際、直前の仕事 \(i-1\) を選んでいたかどうかによって、ペナルティ \(K\) が発生するかが決まります。このように、直前の状態が現在の選択に影響を与える問題は、動的計画法 (DP) を用いて効率的に解くことができます。

重要なポイント

1. 状態の定義: 仕事 \(i\) まで見たときに、仕事 \(i\) を「選んだ状態」と「選んでいない状態」の 2 つを保持する必要があります。
2. 「1 つ以上選ぶ」という制約: すべての \(A_i\) が正の整数であるため、最終的な利益は必ず正になります。そのため、初期状態として「まだ何も選んでいない状態」を適切に扱うか、非常に小さな値（\(-\infty\)）で初期化することで、この制約をクリアできます。
3. 遷移の考え方:
   • 仕事 \(i\) を選ばない場合：仕事 \(i-1\) を選んでいてもいなくても、それまでの最大利益を引き継ぎます。
   • 仕事 \(i\) を選ぶ場合：
     • 仕事 \(i\) を最初に選ぶ仕事にする（利益：\(A_i\)）
     • 仕事 \(i-1\) は選ばず、仕事 \(i\) を選ぶ（利益：\(dp[i-1][\text{不選択}] + A_i\)）
     • 仕事 \(i-1\) も選んでおり、仕事 \(i\) も選ぶ（利益：\(dp[i-1][\text{選択}] + A_i - K\)）

アルゴリズム

以下の 2 つの状態を持つ DP を行います。

• dp0: 仕事 \(i\) を選ばないときの、仕事 \(1 \dots i\) における利益の最大値
• dp1: 仕事 \(i\) を選ぶときの、仕事 \(1 \dots i\) における利益の最大値

遷移式

各 \(i = 1, \dots, N-1\) について、前のステップの値を prev_dp0, prev_dp1 とすると：

1. dp0 = max(prev_dp0, prev_dp1)
   • 仕事 \(i\) を選ばないため、ペナルティは発生しません。単純に \(i-1\) までの最大値を選びます。
2. dp1 = max(A[i], prev_dp0 + A[i], prev_dp1 + A[i] - K)
   • A[i]: 仕事 \(i\) を最初の 1 つ目として選ぶ場合
   • prev_dp0 + A[i]: 前を選んでおらず、今回選ぶ場合
   • prev_dp1 + A[i] - K: 前も選んでおり、今回も選ぶ場合（ペナルティ \(K\) が発生）

最後に max(dp0, dp1) が答えとなります。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の仕事を 1 回ずつ走査し、各ステップで定数時間の計算を行うためです。
• 空間計算量: \(O(1)\)
  • 直前の状態（prev_dp0, prev_dp1）のみを保持すればよいため、配列を使わず変数のみで実装可能です（報酬の入力リスト \(A\) を除いた場合）。

実装のポイント

• 初期値: 最初の仕事（\(i=0\)）について、dp0 は「まだ何も選んでいない」ことを示すために \(-\infty\) とし、dp1 は A[0] とします。

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• ペナルティの扱い: 仕事を \(m\) 個連続で選んだとき、ペアの数は \(m-1\) 個になるため、遷移式の prev_dp1 + A[i] - K で正しくペナルティを引くことができます。”`markdown

  概要

  \(N\) 個の仕事から 1 つ以上を選び、報酬の合計から「連続して選んだペアの数 \(\times K\)」を引いた利益を最大化する問題です。

考察

各仕事 \(i\) について「選ぶ」か「選ばない」かを決める際、直前の仕事 \(i-1\) を選んでいたかどうかによって、ペナルティ \(K\) が発生するかが決まります。このように、直前の状態が現在の選択に影響を与える問題は、動的計画法 (DP) を用いて効率的に解くことができます。

重要なポイント

1. 状態の定義: 仕事 \(i\) まで見たときに、仕事 \(i\) を「選んだ状態」と「選んでいない状態」の 2 つを保持する必要があります。
2. 「1 つ以上選ぶ」という制約: すべての \(A_i\) が 1 以上の整数であるため、最終的な利益は必ず正になります。初期状態として「まだ何も選んでいない状態」を適切に扱う（非常に小さな値 \(-\infty\) で初期化する）ことで、この制約を自然に満たすことができます。
3. 遷移の考え方:
   • 仕事 \(i\) を選ばない場合：仕事 \(i-1\) を選んでいてもいなくても、それまでの最大利益を引き継ぎます。
   • 仕事 \(i\) を選ぶ場合：
     • 仕事 \(i\) を最初に選ぶ仕事にする（利益：\(A_i\)）
     • 仕事 \(i-1\) は選ばず、仕事 \(i\) を選ぶ（利益：\(dp[i-1][\text{不選択}] + A_i\)）
     • 仕事 \(i-1\) も選んでおり、仕事 \(i\) も選ぶ（利益：\(dp[i-1][\text{選択}] + A_i - K\)）

アルゴリズム

以下の 2 つの状態を持つ DP を行います。

• dp0: 仕事 \(i\) を選ばないときの、仕事 \(1 \dots i\) における利益の最大値
• dp1: 仕事 \(i\) を選ぶときの、仕事 \(1 \dots i\) における利益の最大値

遷移式

各 \(i = 1, \dots, N-1\) について、前のステップの値を prev_dp0, prev_dp1 とすると：

1. dp0 = max(prev_dp0, prev_dp1)
   • 仕事 \(i\) を選ばないため、ペナルティは発生しません。単純に \(i-1\) までの最大値を選びます。
2. dp1 = max(A[i], prev_dp0 + A[i], prev_dp1 + A[i] - K)
   • A[i]: 仕事 \(i\) を最初の 1 つ目として選ぶ場合
   • prev_dp0 + A[i]: 前を選んでおらず、今回選ぶ場合
   • prev_dp1 + A[i] - K: 前も選んでおり、今回も選ぶ場合（ペナルティ \(K\) が発生）

最後に max(dp0, dp1) が答えとなります。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の仕事を 1 回ずつ走査し、各ステップで定数時間の計算を行うためです。
• 空間計算量: \(O(N)\)
  • 入力配列 \(A\) の保持に \(O(N)\) かかります。DP の遷移自体は \(O(1)\) の追加空間（変数のみ）で実装可能です。

実装のポイント

• 初期値: 最初の仕事（\(i=0\)）について、dp0 は「まだ何も選んでいない」ことを示すために \(-\infty\) とし、dp1 は A[0] とします。
• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。
• ペナルティの扱い: 仕事を \(m\) 個連続で選んだとき、ペアの数は \(m-1\) 個になるため、遷移式の prev_dp1 + A[i] - K で正しくペナルティを計算できます。

## ソースコード

```python
import sys

def solve():
    # Fast I/O: read all input at once and split into tokens
    # This is more efficient for large inputs in competitive programming.
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of jobs, K: penalty per continuous pair
    N = int(input_data[0])
    K = int(input_data[1])
    
    # A: rewards for each job A_1, A_2, ..., A_N
    # list(map(int, ...)) is efficient for converting tokens to integers.
    A = list(map(int, input_data[2:]))
    
    # dp0: Maximum profit considering jobs 1 to i, where job i is NOT selected.
    #      We use -inf to ensure that the "at least one job" requirement is handled.
    # dp1: Maximum profit considering jobs 1 to i, where job i IS selected.
    
    # Base case: the first job (index 0)
    # Since A_i >= 1, the maximum profit will always be positive.
    inf = 10**18
    dp0 = -inf
    dp1 = A[0]
    
    # DP transitions for jobs i = 1 to N-1
    for i in range(1, N):
        # Store values from the previous step (job i-1)
        prev_dp0 = dp0
        prev_dp1 = dp1
        
        # Transition for not selecting job i:
        # We take the maximum profit achievable from the first i-1 jobs.
        dp0 = max(prev_dp0, prev_dp1)
        
        # Transition for selecting job i:
        # There are three sub-cases for selecting job i:
        # 1. Job i is the first job selected in the sequence.
        # 2. Job i is selected, and some job(s) from the first i-1 were selected, 
        #    but job i-1 was NOT selected.
        # 3. Job i is selected, and job i-1 WAS selected (incurring a penalty K).
        
        # Combining Case 1 and Case 2: A[i] + max(0, prev_dp0)
        # Note: Since A_i >= 1, finite prev_dp0 is always >= 1.
        
        dp1 = max(A[i], prev_dp0 + A[i], prev_dp1 + A[i] - K)
        
    # The final answer is the maximum of the two states after considering all N jobs.
    print(max(dp0, dp1))

if __name__ == '__main__':
    solve()

---

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