概要

飛び石 \(1\) から \(N\) まで移動する際、最大 \(K\) 回のスキップ（一つ飛ばし）を使って、訪れる飛び石のスコア合計を最大化する問題です。「非隣接な要素を最大 \(K\) 個選んで和を最大化する」古典的な問題に帰着できます。

考察

重要な気づき①：スキップは「石を1つ飛ばす」こと

スキップを一切使わなければ、すべての石を訪れるのでスコアの合計は \(\sum_{i=1}^{N} A_i\) です。スキップを使うと、ちょうど1つの石を飛ばせます。飛び石 \(j\) を飛ばすと、スコア合計から \(A_j\) が引かれる（= \(-A_j\) が加算される）ことになります。

重要な気づき②：隣接する2つの石は同時にスキップできない

飛び石 \(j\) を飛ばすとは、\(j-1\) から \(j+1\) へジャンプすることです。もし \(j+1\) も飛ばしたいなら、\(j\) から \(j+2\) へジャンプする必要がありますが、\(j\) 自体を訪れていないので不可能です。したがって、隣接する2つの石を同時にスキップすることはできません。

問題の言い換え

飛び石 \(1\) と \(N\) は必ず訪れるので、スキップ候補は石 \(2, 3, \ldots, N-1\) です。各石 \(j\) をスキップしたときの「利得」を \(B_j = -A_j\) とすると：

配列 \(B\) から非隣接な要素を最大 \(K\) 個選び、その和を最大化せよ。

素朴な DP のTLE

\(dp[i][k]\) =「最初の \(i\) 個から \(k\) 個選んだときの最大和」とすれば \(O(NK)\) ですが、\(N, K\) ともに最大 \(2 \times 10^5\) なので最悪 \(O(N^2)\) となりTLEします。

アルゴリズム

ヒープ＋連結リストによる貪欲法を使います。これは「非隣接 \(K\) 個選択で最大和」を \(O(N \log N)\) で解く古典的テクニックです。

手順

1. 各要素を双方向連結リストで管理し、値を最大ヒープに入れる。
2. ヒープから最大値の要素 \(idx\) を取り出す。値が \(0\) 以下なら終了。
3. その値を利得に加算する。
4. マージ操作：要素 \(idx\) の左隣 \(p\) と右隣 \(n\) を「使用済み」にし、\(idx\) の値を以下に更新する： $\(\text{val}[idx] \leftarrow \text{val}[p] + \text{val}[n] - \text{val}[idx]\)\( この新しい値は「\)idx\( の選択を取り消して、代わりに \)p\( と \)n$ の両方を選ぶ」差分利得を表す。
5. 更新後の \(idx\) をヒープに戻し、連結リストを繋ぎ直す。
6. \(K\) 回選択するか、正の利得がなくなるまで繰り返す。

具体例

\(A = [3, -5, -8, 4, 7]\), \(K = 2\) の場合： - 全石の合計 = \(3 + (-5) + (-8) + 4 + 7 = 1\) - スキップ候補：石2, 3, 4 → 利得 \(B = [5, 8, -4]\) - 1回目：\(B[1]=8\) を選択（石3をスキップ）→ 利得 \(+8\)、マージ後 \(B[1] = 5+(-4)-8 = -7\) - 2回目：\(B[0]=5\) を選択（石2をスキップ）→ 利得 \(+5\) - 合計：\(1 + 8 + 5 = 14\)（石2,3をスキップ…？）

ここでの注意：\(B[0]\) と \(B[1]\) は隣接ですが、マージ操作により「\(B[1]\)を選んだ後に新しい\(B[1]=-7\)を選ぶ」＝「\(B[1]\)の選択を取り消して\(B[0]\)と\(B[2]\)を選ぶ」と同義です。アルゴリズムは正しく非隣接制約を守ります。

計算量

• 時間計算量: \(O(N \log N)\)（ヒープ操作が支配的）
• 空間計算量: \(O(N)\)（連結リスト・ヒープ用）

実装のポイント

• removed配列：ヒープから取り出した要素が既にマージで消されていないか確認する（遅延削除）。

• 連結リストの境界処理：先頭・末尾の要素には左隣・右隣が存在しない場合があるので、条件分岐が必要。

• マージ時の新しい値：\(\text{val}[p] + \text{val}[n] - \text{val}[idx]\) という更新式が「取り消し＋代替選択」を正しく表現する核心部分。

• 早期終了：利得が \(0\) 以下になったらそれ以上スキップしても損するだけなので即座に終了。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    if N <= 2:
        print(A[0] + A[N - 1] if N == 2 else A[0])
        return
    
    # dp[i][k] = max score to reach stone i using exactly k skips
    # This is O(N*K) which could be up to 2*10^5 * 2*10^5 = 4*10^10, too large.
    
    # Better approach: Think about which stones to skip.
    # Without any skips, we visit all stones and get sum(A).
    # Each skip skips exactly one stone (stone i+1 when jumping from i to i+2).
    # But skips can't overlap in certain ways.
    # 
    # When we skip stone j (2 <= j <= N-1, since we must visit 1 and N),
    # we save A[j] (i.e., subtract A[j] from the total if A[j] is negative, that helps).
    # Actually, skipping stone j means we DON'T collect A[j], so the gain from skipping j is -A[j].
    # We want to maximize total, so we want to skip stones with the most negative A[j] values,
    # i.e., skip stones where -A[j] is largest, i.e., A[j] is most negative.
    #
    # BUT: constraint is that we can't skip two adjacent stones. If we skip stone j,
    # we jump from j-1 to j+1. If we also skip stone j+1, we'd need to jump from j-1 to j+2,
    # but that's a jump of 3, which isn't allowed. So no two consecutive stones can be skipped.
    #
    # Also, stones 1 and N cannot be skipped.
    #
    # So the problem reduces to: select at most K non-adjacent stones from {2, 3, ..., N-1}
    # to skip, maximizing the sum of (-A[j]) for skipped stones j.
    # Equivalently: select at most K non-adjacent elements from array B where B[j] = -A[j+1]
    # for j = 0..N-3 (representing stones 2..N-1), maximize sum of selected elements.
    
    # Total without skipping = sum(A)
    # We add the sum of (-A[j]) for each skipped stone j.
    
    total = sum(A)
    
    # Stones that can be skipped: indices 1 to N-2 (0-indexed), i.e., stones 2 to N-1
    # Values to pick from: B[i] = -A[i+1] for i in 0..N-3... wait let me reindex.
    # Skippable stones (0-indexed): 1, 2, ..., N-2
    # Gain from skipping stone i (0-indexed): -A[i]
    # Select at most K non-adjacent from these, maximize sum of gains.
    
    B = [-A[i] for i in range(1, N - 1)]  # gains for skipping stones 1..N-2 (0-indexed)
    M = len(B)  # = N - 2
    
    if M == 0 or K == 0:
        print(total)
        return
    
    # Now: select at most K non-adjacent elements from B to maximize their sum.
    # We only want to skip stones that give positive gain (B[i] > 0), unless forced.
    # Since K is "at most", we never need to skip a stone with non-positive gain.
    
    # This is the classic "select at most K non-adjacent elements with maximum sum" problem.
    # Can be solved with DP: dp[i][j] = max sum using first i elements with j selected.
    # O(M*K) might be too large.
    
    # Use the greedy algorithm with a heap (similar to the "select K non-adjacent with max sum" 
    # problem solvable in O(M log M) using a linked list + heap approach).
    
    # Actually, let's just do DP with optimization. K can be at most (N-2+1)/2 ~ N/2 effectively.
    # But O(N*K) can be 2*10^10 in worst case.
    
    # Let's use the heap-based greedy approach.
    
    import heapq
    
    # Greedy: repeatedly pick the best available element, then merge neighbors.
    # This is the classic algorithm for selecting K non-adjacent elements with max sum.
    
    INF = float('inf')
    prev_node = list(range(-1, M - 1))
    next_node = list(range(1, M + 1))
    val = list(B)
    removed = [False] * M
    
    heap = [(-B[i], i) for i in range(M)]
    heapq.heapify(heap)
    
    gain = 0
    selected = 0
    
    while selected < K and heap:
        neg_v, idx = heapq.heappop(heap)
        if removed[idx]:
            continue
        v = -neg_v
        if v <= 0:
            break
        gain += v
        selected += 1
        
        p = prev_node[idx]
        n = next_node[idx]
        
        new_val = -v
        if p >= 0:
            new_val += val[p]
            pp = prev_node[p]
            removed[p] = True
            if pp >= 0:
                next_node[pp] = idx
            prev_node[idx] = pp
        else:
            prev_node[idx] = -1
        
        if n < M:
            new_val += val[n]
            nn = next_node[n]
            removed[n] = True
            if nn < M:
                prev_node[nn] = idx
            next_node[idx] = nn
        else:
            next_node[idx] = M
        
        val[idx] = new_val
        heapq.heappush(heap, (-new_val, idx))
    
    print(total + gain)

solve()

---

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