D - 花壇づくりのボーナス / Bonus for Flower Bed Making 解説 by admin
gemini-3.5-flash-thinking概要
この問題は、予算 \(W\) の制限のもとで、選んだ区画の「美しさ」の合計と、連続して選んだ区画（極大連続区間）の長さに応じて得られる「ボーナス美しさ」の和を最大化する問題です。 古典的な「ナップサック問題」に、隣接する要素を選択したときのボーナス条件が加わった、動的計画法（DP）を用いる問題です。
考察
1. 単純なナップサック問題との違い
通常のナップサック問題では、各アイテムを「選ぶ」か「選ばない」かで得られる価値は独立しています。しかし、この問題では「直前に選んだ区画があるか、そしてそれがどれだけ連続しているか」によって、新しく区画を選んだときに得られるボーナス美しさが変化します。
2. ボーナスの発生条件の整理
極大連続区間の長さを \(L\) としたとき、得られるボーナスは以下のようになります。 - \(L = 1\) のとき: \(0\) - \(L = 2\) のとき: \(2 \times B\) - \(L = 3\) のとき: \(3 \times B\) - \(L \geq 2\) のとき: \(L \times B\)
これを、区画を左から順に \(1\) つずつ選んでいく過程でどのように加算すればよいでしょうか？ 直前の状態（連続している長さ）に応じて、新しく区画 \(i\) を選んだときのボーナスの加算方法を次のように設計します。
- 直前に区画を選んでいない（現在の連続長さが \(0\)）場合
- 新しく区画 \(i\) を選ぶと、連続長さは \(1\) になります。
- この時点ではボーナスは発生しないため、加算される値は区画 \(i\) の美しさ \(D_i\) のみです。
- 直前の連続長さが \(1\) の場合
- 新しく区画 \(i\) を選ぶと、連続長さは \(2\) になります。
- 長さが \(2\) になったことで、これまでの分も含めて \(2 \times B\) のボーナスが一気に発生します。
- したがって、加算される値は \(D_i + 2 \times B\) となります。
- 直前の連続長さが \(2\) 以上の場合
- 新しく区画 \(i\) を選ぶと、連続長さが \(1\) 増えます（例えば \(2 \to 3\) ）。
- 長さが \(1\) 増えるごとに、追加で \(B\) のボーナスが発生します。
- したがって、加算される値は \(D_i + B\) となります。
このように考えると、覚えるべき「直前の状態」は、具体的な長さではなく、「\(0\)（選んでいない）」「\(1\)（長さ \(1\)）」「\(2\)（長さ \(2\) 以上）」の3つの状態だけで十分であることが分かります。
アルゴリズム
動的計画法（DP）を用いて解きます。
DPテーブルの定義
dp[w][s]:= これまでに選んだ区画の費用の合計が \(w\) であり、現在の最後の区画の連続状態が \(s\) であるときの、美しさ（ボーナス含む）の最大値。
ここで、状態 \(s\) は以下の3つの値を取ります： - \(s = 0\) : 直前の区画を選んでいない（現在の連続長さが \(0\)） - \(s = 1\) : 現在の連続長さが \(1\) - \(s = 2\) : 現在の連続長さが \(2\) 以上
初期状態
dp[0][0] = 0- それ以外のすべての
dp[w][s]は \(-\infty\)（到達不可能を表す）
遷移
区画 \(i\) (\(0 \leq i < N\)) について、現在の DP テーブルから次の DP テーブル next_dp への遷移を考えます。各 \(w\) (\(0 \leq w \leq W\)) について、以下の遷移を行います。
1. \(s = 0\) からの遷移
- 区画 \(i\) を選ばない場合：
- 状態は \(s = 0\) のままです。費用も美しさも増えません。
next_dp[w][0] = max(next_dp[w][0], dp[w][0])
- 区画 \(i\) を選ぶ場合（\(w + C_i \leq W\) のとき）：
- 状態は \(s = 1\) になり、美しさ \(D_i\) が得られます（ボーナスは \(0\)）。
next_dp[w + C_i][1] = max(next_dp[w + C_i][1], dp[w][0] + D_i)
2. \(s = 1\) からの遷移
- 区画 \(i\) を選ばない場合：
- 連続が途切れるため、状態は \(s = 0\) に戻ります。
next_dp[w][0] = max(next_dp[w][0], dp[w][1])
- 区画 \(i\) を選ぶ場合（\(w + C_i \leq W\) のとき）：
- 連続長さが \(2\) になるため、状態は \(s = 2\) になり、美しさ \(D_i\) とボーナス \(2 \times B\) が得られます。
next_dp[w + C_i][2] = max(next_dp[w + C_i][2], dp[w][1] + D_i + 2 * B)
3. \(s = 2\) からの遷移
- 区画 \(i\) を選ばない場合：
- 連続が途切れるため、状態は \(s = 0\) に戻ります。
next_dp[w][0] = max(next_dp[w][0], dp[w][2])
- 区画 \(i\) を選ぶ場合（\(w + C_i \leq W\) のとき）：
- 連続長さが \(2\) 以上のまま、さらに \(1\) 伸びるため、状態は \(s = 2\) のままで、美しさ \(D_i\) と追加ボーナス \(B\) が得られます。
next_dp[w + C_i][2] = max(next_dp[w + C_i][2], dp[w][2] + D_i + B)
すべての区画について遷移を終えた後、すべての dp[w][s] の中での最大値が答えとなります。
計算量
時間計算量: \(O(N \times W)\) 区画の数 \(N\) に対し、予算 \(W\) と状態数 \(3\) のループを回すため、全体の計算量は \(O(3 \times N \times W) = O(NW)\) となります。 制約は \(N \leq 2000\), \(W \leq 20000\) であるため、総計算回数は約 \(1.2 \times 10^8\) 回となり、実行時間制限内に十分間に合います。
空間計算量: \(O(W)\) DPテーブルは、直前のステップ（区画 \(i-1\) まで）の情報だけがあれば次のステップを計算できます。そのため、サイズ \(O(W)\) の配列を2つ（
dpとnext_dp）用意して交互に使い回す（スワップする）ことで、空間計算量を \(O(W)\) に抑えることができます。
実装のポイント
初期化の注意: 美しさの最大値を求めるため、初期値は十分に小さな値（\(-\infty\)）で初期化する必要があります。C++では
1e18などの十分大きな値をINFと定義し、-INFで初期化すると安全です。メモリの節約:
vector<vector<long long>> dp(W + 1, vector<long long>(3, -INF))のように、現在の行と次の行の2行分だけを保持することで、空間計算量を劇的に削減し、キャッシュ効率も向上させることができます。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
int main() {
// Optimize standard I/O operations for speed
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, W;
long long B;
if (!(cin >> N >> W >> B)) return 0;
vector<long long> D(N);
vector<int> C(N);
for (int i = 0; i < N; ++i) {
cin >> D[i] >> C[i];
}
// dp[w][s]
// s = 0: current segment length is 0 (last item not chosen)
// s = 1: current segment length is 1
// s = 2: current segment length is >= 2
vector<vector<long long>> dp(W + 1, vector<long long>(3, -INF));
vector<vector<long long>> next_dp(W + 1, vector<long long>(3, -INF));
dp[0][0] = 0;
for (int i = 0; i < N; ++i) {
for (int w = 0; w <= W; ++w) {
next_dp[w][0] = -INF;
next_dp[w][1] = -INF;
next_dp[w][2] = -INF;
}
long long cur_D = D[i];
int cur_C = C[i];
for (int w = 0; w <= W; ++w) {
// Transition from s = 0
if (dp[w][0] != -INF) {
// Option 1: Do not choose flowerbed i
if (dp[w][0] > next_dp[w][0]) {
next_dp[w][0] = dp[w][0];
}
// Option 2: Choose flowerbed i
if (w + cur_C <= W) {
long long val = dp[w][0] + cur_D;
if (val > next_dp[w + cur_C][1]) {
next_dp[w + cur_C][1] = val;
}
}
}
// Transition from s = 1
if (dp[w][1] != -INF) {
// Option 1: Do not choose flowerbed i
if (dp[w][1] > next_dp[w][0]) {
next_dp[w][0] = dp[w][1];
}
// Option 2: Choose flowerbed i
if (w + cur_C <= W) {
long long val = dp[w][1] + cur_D + 2 * B;
if (val > next_dp[w + cur_C][2]) {
next_dp[w + cur_C][2] = val;
}
}
}
// Transition from s = 2
if (dp[w][2] != -INF) {
// Option 1: Do not choose flowerbed i
if (dp[w][2] > next_dp[w][0]) {
next_dp[w][0] = dp[w][2];
}
// Option 2: Choose flowerbed i
if (w + cur_C <= W) {
long long val = dp[w][2] + cur_D + B;
if (val > next_dp[w + cur_C][2]) {
next_dp[w + cur_C][2] = val;
}
}
}
}
dp.swap(next_dp);
}
long long ans = 0;
for (int w = 0; w <= W; ++w) {
for (int s = 0; s < 3; ++s) {
ans = max(ans, dp[w][s]);
}
}
cout << ans << "\n";
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
投稿日時:
最終更新: