E - 果物の収穫 / Fruit Harvest 解説 by admin
Claude Opus 5 (High)概要
各木 \(i\) には「初期値 \(A_i\)・1 日ごとの減少量 \(D_i\)（ただし \(0\) 未満にはならない）」の果物があり、\(K\) 日間で \(K\) 本の木を選んで 1 本ずつ収穫するとき、得られる美味しさの総和を最大化する問題です。
「どの木を選ぶか」と「どの順で収穫するか」を同時に決める必要がありますが、順番は \(D\) の降順が最適という交換論法を使うと、ソート + ナップサック型 DP で解けます。
考察
素朴なアプローチ
\(N\) 本から \(K\) 本を選んで並べる方法は \(\frac{N!}{(N-K)!}\) 通りあり、\(N \le 5000\) では全探索は到底不可能です。また、単純に「\(A_i\) が大きい順」「\(D_i\) が大きい順」に \(K\) 本選ぶような貪欲は反例が作れます（例：\(A\) が大きくても \(D\) が大きすぎてすぐ 0 になる木は、後半に回せば無価値）。
重要な観察 1：収穫順は \(D\) の降順
まず、\(\max(0,\cdot)\) を一旦無視して考えます。木 \(i\) を \(t_1\) 日目、木 \(j\) を \(t_2\) 日目（\(t_1 < t_2\)）に取るとき、2 つの合計は
\[\bigl(A_i - (t_1-1)D_i\bigr) + \bigl(A_j - (t_2-1)D_j\bigr)\]
で、入れ替えた場合との差は \((t_2 - t_1)(D_i - D_j)\) です。よって \(D_i \ge D_j\) なら「\(D\) が大きい方を先に取る」方が得（同じか良い）です。隣接交換を繰り返せば、\(D\) の降順に収穫するのが最適と言えます。
\(\max(0,\cdot)\) のクリップがあっても、クリップは値を増やす方向にしか働かないので、「クリップなしの最適値 \(\le\) クリップ後の値」より、\(D\) 降順に並べ替えて損はありません。
重要な観察 2：「美味しさ 0 の果物」は無視して詰めてよい
ここで注意が必要です。上の交換論法は「両方の値が正」の状況では素直ですが、途中で 0 にクリップされる木があると話が変わります。例えば
- 木1: \(A=1, D=10\)、木2: \(A=10, D=9\)、\(K=2\)
の場合、\(D\) 降順（木1 → 木2）だと \(1 + \max(0,10-9) = 2\) ですが、実は木2 を 1 日目に取れば \(10 + \max(0,1-10) = 10\) が最適です。
これをどう扱うかというと、次のように考えます。最適解のうち、実際に正の値を得ている木だけを取り出し、それらを（相対順を保ったまま）1 日目, 2 日目, …, \(m\) 日目に前詰めします。日付が早くなると値は減らないので、総和は悪化しません。残りの \(K-m\) 本は後半の日に回し、その寄与は \(0\) 以上です。
こうして得られる配置では「選ばれた \(m\) 本すべてが正の値」なので、観察 1 の交換論法がそのまま使え、\(D\) 降順に並べ替えても総和は減りません。
したがって、
ある \(m\)（\(0 \le m \le K\)）が存在し、「\(D\) 降順に並べた列から \(m\) 本を選び、選んだ \(r\) 番目を \(r\) 日目に収穫する」形で最適値が達成できる
が成り立ちます。逆にこの形の値はいずれも実現可能（残りの日は未収穫の木で埋めれば寄与は \(0\) 以上）なので、すべての \(m\) について最大を取れば答えになります。
アルゴリズム
- 全ての木を \(D_i\) の降順にソートする（\(D\) が等しいときの順序は任意でよい：同じ \(D\) のグループ内では日付の割り当てを入れ替えても合計 \(\sum A - D\sum (t-1)\) は変わらないため）。
- ナップサック型 DP を行う。
- \(dp[j]\) = ソート後の先頭から順に見て、これまでに \(j\) 本選んだときの美味しさの最大値（\(j\) 本目に選んだ木は \(j\) 日目に収穫する）
- 初期値：\(dp[0]=0\)、\(dp[j]=-\infty\ (j \ge 1)\)
- 遷移（\(i\) 番目の木 \((A,D)\) を見るとき、\(j\) を大きい方から回す）： $\(dp[j] \leftarrow \max\bigl(dp[j],\ dp[j-1] + \max(0, A - (j-1)D)\bigr)\)$
- 答えは \(\max_{0 \le j \le K} dp[j]\)。
例
\(N=2, K=2\)、木1 \((A,D)=(1,10)\)、木2 \((A,D)=(10,9)\) の場合。
ソート後：\((A,D) = (1,10), (10,9)\)。
- 木 \((1,10)\)：\(dp[1] = 0 + 1 = 1\)
- 木 \((10,9)\)：\(dp[2] = dp[1] + \max(0,10-9) = 2\)、\(dp[1] = \max(1, 0+10) = 10\)
\(\max(dp[0],dp[1],dp[2]) = \max(0,10,2) = 10\) となり、正しい答えが得られます。ここで \(dp[K]=dp[2]=2\) だけを見ると誤答になることに注意してください。
計算量
- 時間計算量: \(O(N \log N + NK)\)（\(N,K \le 5000\) なので最大 \(2.5\times 10^7\) 回程度の更新で十分高速）
- 空間計算量: \(O(N + K)\)
実装のポイント
必ず \(\max_j dp[j]\) を答えにする（\(dp[K]\) だけでは不足）。これは「美味しさ 0 になる果物を混ぜる」ケースを表現するためです。
1 次元 DP で \(j\) を降順に回すこと（各木を 1 回しか使わない 0-1 ナップサック）。
オーバーフロー対策：\((j-1)\times D\) は最大 \(5000 \times 10^9 = 5\times10^{12}\)、答えも最大 \(5\times10^{12}\) 程度になるので 64bit 整数（
long long）を使う。遷移時に
max(0, A - (j-1)*D)のクリップを忘れない（値が負の木を選んでも実際には \(0\)）。\(dp[j]\) が未到達（\(-\infty\)）の場合はスキップする。センチネルは加算してもオーバーフローしない値（例：
LLONG_MIN/4）にしておくと安全。入出力が最大 5000 行なので、
scanf/高速入力を使うと安心（Python ならsys.stdinを利用）。ソースコード
#include <bits/stdc++.h>
using namespace std;
int main(){
int N, K;
if(scanf("%d %d", &N, &K)!=2) return 0;
vector<pair<long long,long long>> v(N); // (D, A)
for(int i=0;i<N;i++){
long long a,d;
scanf("%lld %lld",&a,&d);
v[i] = {d,a};
}
// sort by D descending
sort(v.begin(), v.end(), [](const pair<long long,long long>&x, const pair<long long,long long>&y){
if(x.first != y.first) return x.first > y.first;
return x.second > y.second;
});
const long long NEG = LLONG_MIN/4;
vector<long long> dp(K+1, NEG);
dp[0] = 0;
for(int i=1;i<=N;i++){
long long D = v[i-1].first;
long long A = v[i-1].second;
int jmax = min(K, i);
for(int j=jmax;j>=1;j--){
if(dp[j-1] == NEG) continue;
long long val = A - (long long)(j-1)*D;
if(val < 0) val = 0;
long long cand = dp[j-1] + val;
if(cand > dp[j]) dp[j] = cand;
}
}
long long ans = 0;
for(int j=0;j<=K;j++) if(dp[j] != NEG) ans = max(ans, dp[j]);
printf("%lld\n", ans);
return 0;
}
この解説は claude5opus-high によって生成されました。
投稿日時:
最終更新: