概要

本棚から本を取り除いて、残った本のページ数が狭義単調増加になるようにしたい。取り除く本の手数料の合計を最小化する問題です。これは「残す本のコストの合計を最大化する」問題に言い換えることで、最長増加部分列（LIS）の変種として解けます。

考察

問題の言い換え

取り除く本の手数料の合計を最小化したいので、逆に考えると 残す本の手数料の合計を最大化 すればよいです。

\[\text{答え} = \text{全本の手数料合計} - \text{残す本の手数料合計の最大値}\]

「残す本」の条件は、ページ数が狭義単調増加になる部分列であることです。つまり、ページ数が狭義単調増加な部分列の中で、手数料 \(C_i\) の合計が最大となるものを求める 問題に帰着されます。

具体例で理解する

例えば \(N = 4\)、ページ数 \(A = [3, 1, 4, 2]\)、手数料 \(C = [10, 1, 5, 2]\) の場合を考えます。

• 部分列 \([3, 4]\)（インデックス 1, 3）を残す → 手数料合計 \(10 + 5 = 15\)、取り除くコスト \(1 + 2 = 3\)
• 部分列 \([1, 4]\)（インデックス 2, 3）を残す → 手数料合計 \(1 + 5 = 6\)、取り除くコスト \(10 + 2 = 12\)

前者のように手数料が高い本をなるべく残せば、取り除くコストが小さくなります。

素朴なアプローチ

全ての部分集合を試すと \(O(2^N)\) で、\(N \leq 5000\) では到底間に合いません。動的計画法（DP）を使います。

アルゴリズム

LIS（最長増加部分列）と同様のDPを用います。ただし「長さの最大化」ではなく「手数料合計の最大化」を行います。

DP定義:

\[dp[i] = \text{インデックス } i \text{ の本を最後に残す狭義単調増加部分列における、手数料合計の最大値}\]

遷移:

\[dp[i] = C_i + \max\left(\{0\} \cup \{dp[j] \mid j < i \text{ かつ } A_j < A_i\}\right)\]

• \(A_j < A_i\) を満たす \(j < i\) が存在する場合、その中で \(dp[j]\) が最大のものに \(C_i\) を加えます。
• そのような \(j\) がなければ、本 \(i\) だけからなる部分列で \(dp[i] = C_i\) です。

答え:

\[\text{答え} = \sum_{i=1}^{N} C_i - \max_{0 \leq i < N} dp[i]\]

\(N \leq 5000\) なので、二重ループの \(O(N^2)\) で十分間に合います。

計算量

• 時間計算量: \(O(N^2)\) — 各 \(i\) に対して \(j = 0, 1, \ldots, i-1\) を走査するため
• 空間計算量: \(O(N)\) — DP配列と入力配列の分

実装のポイント

• 最小化ではなく最大化に変換するのがこの問題の核心です。「取り除くコストの最小化」を直接DPするのは難しいですが、「残すコストの最大化」に変換すると、LIS風のDPにきれいに落ちます。

• 全ての本を取り除く（\(0\) 冊残す）場合も許されるので、\(dp\) の最大値が \(0\) になるケースはありませんが（\(C_i \geq 1\) なので少なくとも \(1\) 冊は残す方が良い）、論理的には問題ありません。

• \(C_i\) や合計が大きくなり得るため、64ビット整数が必要です。Pythonでは整数のオーバーフローがないため、特に気にする必要はありません。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    C = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    total_cost = sum(C)
    
    # We want to find a strictly increasing subsequence that maximizes the sum of C
    # (i.e., we keep those books and remove the rest).
    # Answer = total_cost - max sum of C over all strictly increasing subsequences.
    
    # dp[i] = maximum sum of C for a strictly increasing subsequence ending at index i
    # dp[i] = C[i] + max(dp[j] for j < i and A[j] < A[i]), or C[i] if no such j
    
    # N <= 5000, so O(N^2) is fine.
    
    dp = [0] * N
    for i in range(N):
        dp[i] = C[i]
        for j in range(i):
            if A[j] < A[i]:
                dp[i] = max(dp[i], dp[j] + C[i])
    
    max_keep = max(dp)
    print(total_cost - max_keep)

main()

---

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