E - 果物の収穫 / Fruit Harvest Editorial by admin
Claude Opus 5 (High)概要
\(N\) 本の木から \(K\) 本を選び、それぞれを \(1\)〜\(K\) 日目のどこかに割り当てて（1 日 1 本）、\(\max(0, A_i-(t-1)D_i)\) の総和を最大化する問題です。「\(D\) の大きい木から先に収穫する」という並べ替えの性質に気づくと、\(O(NK)\) の DP で解けます。
考察
素朴な方法では無理
「どの \(K\) 本を選ぶか」だけでも \(\binom{N}{K}\) 通り、さらに「どの木を何日目にするか」の割り当ても含めると爆発的です。これは最小費用流やハンガリアン法で解ける「割当問題」でもありますが、\(N=5000\) では計算量的に間に合いません。
また、単純な貪欲（毎日「今日の値が最大の果物」を取る）も失敗します。例えば
- 木1: \(A=10,\ D=0\)
- 木2: \(A=11,\ D=100\)
で \(K=2\) のとき、\(1\) 日目に木1（値 \(10\)）を取ると木2 は \(2\) 日目に \(\max(0,11-100)=0\) となり合計 \(10\)。正解は \(1\) 日目に木2（\(11\)）、\(2\) 日目に木1（\(10\)）で \(21\) です。
鍵となる観察：収穫順は \(D\) の降順
主張：最適解のうち、「実際に正の美味しさが得られた果物」は、\(D\) の大きいものから順に（早い日に）収穫されているものが存在する。
理由（交換論法）：最適解で木 \(u\) を \(t\) 日目、木 \(v\) を \(t'\) 日目（\(t<t'\)）に収穫し、両方の値が正で、かつ \(D_u < D_v\) だとします。\(s=t'-t\) として \(u\) と \(v\) の日を入れ替えると
- \(v\) は \(s\) 日早くなる：\(t'\) 日目の値が正だったので \(t\) 日目でも正であり、値はちょうど \(s\cdot D_v\) 増える。
- \(u\) は \(s\) 日遅くなる：値の減少は \(s\cdot D_u\) 以下（\(0\) で打ち切られるので、減る量はこれ以下）。
よって合計は少なくとも \(s(D_v-D_u)>0\) だけ増え、最適性に矛盾します。つまり最適解では「値が正の収穫」は \(D\) の降順に並んでいます。
値が \(0\) になる日はどうするか
値が \(0\) になる木は「どの木を割り当てても \(0\)」なので、その日は DP 上は「空き」として扱ってよいです。\(N \ge K\) なので、空き日には必ず未収穫の木を割り当てられ、その値は \(0\) 以上なので損はしません（逆に DP の値は実際に達成可能）。
したがって問題は次のように言い換えられます：
木を \(D\) の降順に並べる。この順序を保ったまま、いくつかの木を選び、選んだ順に増加する日 \(t_1<t_2<\cdots\)（\(t_i \le K\)）を割り当てて、値（正のもののみ）の総和を最大化する。
これは LCS 型（部分列マッチング型）の DP で解けます。
アルゴリズム
- 全ての木を \(D\) の降順にソートする。
- \(dp[i][j]\) = 先頭 \(i\) 本の木を見終わり、\(1\)〜\(j\) 日目までを使い切った（一部の日は空きでよい）ときの最大合計値。
遷移は 3 通り： - 木 \(i\) を使わない：\(dp[i-1][j]\) - \(j\) 日目を空きにする：\(dp[i][j-1]\) - 木 \(i\) を \(j\) 日目に収穫する：\(dp[i-1][j-1] + \max(0,\ A_i-(j-1)D_i)\)
$\(dp[i][j]=\max\bigl(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]+\max(0,A_i-(j-1)D_i)\bigr)\)\( 3. 答えは \)dp[N][K]$。
\(i\) の次元は 1 次元配列で使い回せます（\(j\) を小さい順に走査し、更新前の \(dp[j-1]\)（=\(dp[i-1][j-1]\)）と更新後の \(dp[j-1]\)（=\(dp[i][j-1]\)）の両方を変数で保持します）。
枝刈り
木 \(i\) の値が正である最後の日は $\(jm_i=\min\left(K,\ \left\lfloor\frac{A_i-1}{D_i}\right\rfloor+1\right)\quad (D_i=0 \text{ なら } jm_i=K)\)\( です。\)j>jm_i\( では加算項が \)0\( になるので、遷移は \)dp[j]\leftarrow\max(dp[j],dp[j-1])\( だけになります。\)dp\( は \)j$ について単調非減少なので、一度も更新が起きなくなった時点でそれ以降も更新は起きず、break できます。これにより実際の計算はかなり軽くなります。
計算量
- 時間計算量: \(O(N\log N + NK)\)（ソート＋DP。枝刈りにより実際は \(\sum_i \min(K, A_i/D_i+1)\) 程度）
- 空間計算量: \(O(N+K)\)
実装のポイント
- ソート順：\(D\) の降順。\(D\) が同じ場合の順序は結果に影響しません（コードでは
(D, A)を降順ソート）。 - 1 次元 DP の更新順：\(j=1,2,\dots\) と昇順に回しつつ、
prevに「更新前の \(dp[j-1]\)」（\(=dp[i-1][j-1]\)）newprevに「更新後の \(dp[j-1]\)」（\(=dp[i][j-1]\)）
を持ち、\(dp[j]=\max(dp[j],\ prev+v_j,\ newprev)\) とします。ここを混同すると同じ木を複数日に使ってしまう／空き日を作れないバグになります。
- 値の計算：\(v_j=A_i-(j-1)D_i\) は毎回 v -= d と差分で更新すると速いです。\(j\le jm_i\) の範囲では必ず \(v_j>0\) なので max(0,·) は不要です。
- オーバーフロー：答えは最大 \(5000\times10^9=5\times10^{12}\) 程度。Python では問題ありませんが、C++ 等では long long を使ってください。
- \(D_i=0\) のケース：どの日に取っても値は \(A_i\) のままなので \(jm_i=K\) とします（\(0\) 除算に注意）。
ソースコード
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1])
trees = []
idx = 2
ap = trees.append
for _ in range(n):
a = int(data[idx]); d = int(data[idx+1])
idx += 2
ap((d, a))
trees.sort(reverse=True) # D descending
dp = [0] * (k + 1)
for d, a in trees:
if d == 0:
jm = k
else:
jm = (a - 1) // d + 1
if jm > k:
jm = k
prev = 0 # old dp[j-1]
newprev = 0 # new dp[j-1]
v = a # value at day j (j starts at 1): a - (j-1)*d
j = 1
while j <= jm:
cur = dp[j]
c = prev + v
if c < cur:
c = cur
if c < newprev:
c = newprev
dp[j] = c
newprev = c
prev = cur
v -= d
j += 1
# remaining days: value contribution is 0, just propagate carry
while j <= k:
if dp[j] < newprev:
dp[j] = newprev
j += 1
else:
break
sys.stdout.write(str(dp[k]) + "\n")
main()
この解説は claude5opus-high によって生成されました。
posted:
last update: