【AtCoder】ABC 431 D - Robot Customize

2025-11-11

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 693 / NoviSteps: 2Q / 配点: 400 点

問題概要

頭と体からなるロボットがあり、同時に取り付けられる部品が $N$ 種類ある。

種類 $i$ の部品の重さは $W _ i$ であり、それぞれの部品には頭に取り付けたときと体に取り付けたときで異なる嬉しさがある。種類 $i$ の部品を頭に取り付けたときの嬉しさは $H _ i$ 、体に取り付けたときの嬉しさは $B _ i$ である。

なお、ロボットは頭の重さが体の重さより大きいと倒れてしまう。ここで、頭の重さおよび体の重さはそれぞれ頭もしくは体に取り付けられた部品の重さの合計とする。

高橋くんは、 $N$ 種類の部品をすべて $1$ 個ずつロボットに取り付けたいと思っている。ロボットを倒さないように部品を取り付けたときの、すべての部品の嬉しさの合計としてありえる最大値を求めよ。

制約

$1\le N\le500$
$1\le W _ i\le500\ (1\le i\le N)$
$1\le H _ i\le10 ^ 9\ (1\le i\le N)$
$1\le B _ i\le10 ^ 9\ (1\le i\le N)$
入力はすべて整数

考察

まずは、この問題を定式化してみる。

\begin{align*} \mathrm{Maximize:} \quad & \sum_{i \in \mathrm{head}} H_i + \sum_{j \in \mathrm{body}} B_j \\ \mathrm{s.t.} \quad & \sum_{i \in \mathrm{head}} W_i \leq \sum_{j \in \mathrm{body}} W_j \end{align*}

しかし、これだと添字が $i, j$ の 2 つに分かれてしまっており扱いづらいので、どちらか一つに統一する。ここでは、 $i$ (頭)だけにしてみよう。

目的関数(第 1 式)は、一度全ての部品を体に取り付けたときの嬉しさの合計 $\sum_{i=1}^{N} B_i$ を考えると、頭に取り付ける部品 $i$ については嬉しさが $B_i$ から $H_i$ に変わるので、差分 $H_i - B_i$ を加える形で表せる。

また、制約条件(第 2 式)は、全ての部品の重さの合計を $S = \sum_{i=1}^{N} W_i$ とすると、 $\sum_{j \in \mathrm{body}} W_j = S - \sum_{i \in \mathrm{head}} W_i$ であるから、 $\sum_{i \in \mathrm{head}} W_i \leq \frac{1}{2} S$ と書ける。

したがって、冒頭の定式化は以下のように書き換えられる。

\begin{align*} \mathrm{Maximize:} \quad & \sum_{i=1}^{N} B_i + \sum_{i \in \mathrm{head}} (H_i - B_i) \\ \mathrm{s.t.} \quad & \sum_{i \in \mathrm{head}} W_i \leq \frac{1}{2} S \end{align*}

なお、第 1 式の $\sum_{i=1}^{N} B_i$ は定数なので、実質的には $\sum_{i \in \mathrm{head}} (H_i - B_i)$ を最大化すればよいことになる。

これは、重さ $W_i$ 、価値 $H_i - B_i$ の品物を重さの合計が $\frac{1}{2} S$ 以下になるように選んで価値の合計を最大化する、すなわち典型的なナップザック問題に帰着できる。

あとは、動的計画法でこの問題を解けばよい。

二次元 DP テーブルを以下のように定義する。

$\mathrm{dp}_{i, v} := i$ 番目までの部品までを考えたときに、頭に取り付けた部品の重さの合計が $v$ になるように選んだときの $\underset{i}{\sum} (H_i - B_i)$ の合計の最大値 $(0 \leq i \leq N, 0 \leq v \leq \frac{1}{2} S)$

初期値は $\mathrm{dp}_{0, 0} = 0$ 、その他を $\mathrm{dp}_{0, v} = -\infty$ とする。

漸化式は以下のようになる。

\mathrm{dp}_{i, v} = \begin{cases} \mathrm{dp}_{i-1, v} & (v < W_{i}) \\ \max(\mathrm{dp}_{i-1, v}, \mathrm{dp}_{i-1, v - W_{i}} + (H_{i} - B_{i})) & (v \geq W_{i}) \end{cases}

※ 前者は $i$ 番目の部品を頭に取り付けない場合、後者は頭に取り付ける場合

答えは、 $\underset{0 \leq v \leq \frac{1}{2} S}{\max} \mathrm{dp}_{N, v} + \sum_{i=1}^{N} B_i$ である。

定数部分を加えるのを忘れないように注意すること。

実装例

横着して DP テーブルのサイズを $N \times S$ とすると MLE になる。

実装例では、 $S$ の定義を $S = \frac{1}{2} \sum_{i=1}^{N} W_i$ としていることに注意。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.constexpr long long INFL = 1e+18;
7. 
8.using ll = long long;
9. 
10.template <typename T>
11.inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
12. 
13.// ======================================== //
14. 
15.int main()
16.{
17.    int N;
18.    cin >> N;
19.    vector<ll> W(N), H(N), B(N);
20.    rep(i, 0, N) cin >> W[i] >> H[i] >> B[i];
21. 
22.    ll sum_W = 0, sum_B = 0;
23.    rep(i, 0, N)
24.    {
25.        sum_W += W[i];
26.        sum_B += B[i];
27.    }
28.    ll S = sum_W / 2;
29. 
30.    vector<vector<ll>> dp(N + 1, vector<ll>(S + 1, -INFL));
31.    dp[0][0] = 0;
32.    rep(i, 1, N + 1)
33.    {
34.        rep(v, 0, S + 1)
35.        {
36.            dp[i][v] = dp[i - 1][v];
37.            if (v >= W[i - 1])
38.                chmax(dp[i][v], dp[i - 1][v - W[i - 1]] + (H[i - 1] - B[i - 1]));
39.        }
40.    }
41. 
42.    ll ans = -INFL;
43.    rep(v, 0, S + 1) chmax(ans, dp[N][v]);
44. 
45.    cout << ans + sum_B << endl;
46. 
47.    return 0;
48.}