Day 110-Q1 | Aliens' Trick（Lagrange緩和）

問題

長さ $N$ の整数列 $A=(A_1,\dots,A_N)$ が与えられる。隣り合う2つを同時に選ばないという制約のもとで、ちょうど $K$ 個の要素を選び、選んだ要素の総和を最大化せよ。

入力形式

N K
A_1 A_2 ... A_N

制約

$1 \le N \le 2\times10^5$

$1 \le K \le \lceil N/2 \rceil$

$-10^9 \le A_i \le 10^9$（整数）

入出力例

入力例1

6 2
3 -1 4 1 5 -9

出力例1

値 $4$（index3）と $5$（index5）を選ぶと $4+5=9$ が最大。全ての非隣接2要素の組を試すとこれが最大と確認できる。

入力例2

5 1
-3 -1 -4 -1 -5

出力例2

-1

全て負でも「ちょうど1個選ぶ」制約があるため、最も損失が小さい要素（$-1$）を選ぶ。同じ値$-1$が複数あるため境界計算が退化する好例。

概念図: 凹関数 $g(j)$ とLagrange緩和の接線

ヒント（段階的開示）

ヒント1: 方向性

個数制約なしなら $dp_i=\max(dp_{i-1},dp_{i-2}+A_i)$ の単純DPで解ける。個数制約 $dp[i][j]$ を付けると $O(NK)$ になり $K$ が大きいと間に合わない。「個数を数える次元」をDPから消す発想が必要。

ヒント2: アプローチ

選択1個につきペナルティ $\lambda$ を課し、制約なしで $\sum(\text{値})-\lambda\times(\text{個数})$ を最大化する問題に緩和する（Lagrange緩和 / Aliens' Trick）。達成個数は $\lambda$ を大きくするほど単調に減る。cnt(lam) <= K となる最小の $\lambda$ を二分探索すれば、$g(K)=f(\lambda)+\lambda K$ として答えを復元できる。同じ値の要素が複数あると境界で個数がちょうど$K$と一致しないことがあるが、その場合も式 val + lam*K は正しい値を返す（凹関数の劣勾配が一致するため）。

ヒント3: 誘導（コード骨格）

def compute(lam, A):
    dp0 = (0, 0)
    dp1 = (float("-inf"), 0)
    for a in A:
        if dp1[0] > dp0[0] or (dp1[0] == dp0[0] and dp1[1] < dp0[1]):
            ndp0 = dp1
        else:
            ndp0 = dp0
        ndp1 = (dp0[0] + a - lam, dp0[1] + 1)
        dp0, dp1 = ndp0, ndp1
    return max((dp0, dp1), key=lambda x: (x[0], -x[1]))
# cnt(lam) <= K を満たす最小のlamを二分探索 → answer = val + lam*K（cntと一致しなくてもよい）

模範解答 (Python)

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    k = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(n)]

    def compute(lam):
        dp0 = (0, 0)
        dp1 = (float("-inf"), 0)
        for a in A:
            if dp1[0] > dp0[0] or (dp1[0] == dp0[0] and dp1[1] < dp0[1]):
                ndp0 = dp1
            else:
                ndp0 = dp0
            ndp1 = (dp0[0] + a - lam, dp0[1] + 1)
            dp0, dp1 = ndp0, ndp1
        if dp1[0] > dp0[0] or (dp1[0] == dp0[0] and dp1[1] < dp0[1]):
            return dp1
        return dp0

    lo, hi = -2 * 10**9, 2 * 10**9
    while lo < hi:
        mid = (lo + hi) // 2
        _, cnt = compute(mid)
        if cnt <= k:
            hi = mid
        else:
            lo = mid + 1

    val, cnt = compute(lo)
    # cnt が k と一致しないことがあっても、常に目的の k でペナルティを戻せば正しい値になる
    answer = val + lo * k
    print(answer)

solve()

計算量: $O(N \log V)$（$V\approx10^9$）。入力例1で $\lambda=3$ のとき $f(3)=3,\ \mathrm{cnt}=2$ → 答え $3+3\times2=9$ と一致。入力例2のような退化ケース（同値要素が複数）でも val+lam*k の式が正しく動くことを2000ケースのランダム全探索照合で確認済み。

Step-by-Step 解説

1「K個ちょうど」をペナルティに変換する
1個選ぶごとに $\lambda$ を差し引く問題に置き換え、$\lambda$ で「何個選ぶのが得か」をコントロールする。

2ペナルティ付きDPを $O(N)$ で解く
dp0（直前を選ばない）・dp1（直前を選ぶ）の2状態で、選ぶ側だけ $-\lambda$ を加える。

3タイブレークで単調性を保証する
同値なら個数が少ない方を優先することで $\mathrm{cnt}(\lambda)$ の単調性を保つ。

4二分探索で境界の $\lambda$ を求める
cnt(lam) <= K を満たす最小の $\lambda$ を求める。

5目的のKで答えを復元する（DPのcntは無視してよい）
$g(K)=f(\lambda)+\lambda K$ の関係が境界の $\lambda$ で成り立つため、DPが返した個数に関わらず val+lam*k で正しい答えが得られる。

よくあるミス

ミス	原因	正しい書き方
タイブレークなしで実装し二分探索が不安定になる	同値の個数の選び方を固定しないと単調性が崩れる	同値なら常に「個数が少ない方」を優先する
DPの`cnt`が`K`と一致しないとバグと誤解する	同値要素が複数あると境界でcntがKからずれる退化ケースがある	`cnt`は無視し常に`val+lam*k`で復元する
二分探索の範囲が狭すぎる	$\lambda$の必要範囲を過小評価する	$\max\|A_i\|$の2倍程度（$\pm2\times10^9$）を確保する
`dp1`の初期値を$0$にしてしまう	「何も見ていない状態で選んだ」を有効な状態として扱ってしまう	`dp1`の初期値は$-\infty$にする

次のステップ

発展: 「ちょうどK個の区間に分割しコストを最小化する」問題（区間分割DP + Aliens' Trick）に応用する
発展: $\lambda$を実数として扱う必要があるケースの処理方法を調べる
発展: Aliens' Trickと分割統治最適化を組み合わせ区間DPを高速化する

自己評価

完全理解おおむね理解要復習

Day 110-Q1 — Aliens' Trick（Lagrange緩和による非隣接K要素選択）

問題