AtCoder Beginner Contest 032
Updated:
Source codes
Solutions
D - ナップサック問題
全部真面目に解説する。 $0/1$ ナップザック問題は weakly NP-hard である。すなわち、 $N$ の多項式時間では解く方法は知られていない反面、 $\max v _ i$ や $\max w _ i$ もパラメータに加えると多項式時間で解ける。
データセット 1
$N \leq 30$ の場合、 $O(2^{N / 2})$ の半分全列挙をすればよろしい。 $[0, N/2)$ と $[N/2, N)$ でそれぞれ全列挙する。すなわち vector<tuple<ll, ll>> V; を出力するのだが、 (重さの合計, 価値の合計の最大値) を入れる。
2 つ列挙しておいて、一方は昇順に並べ、一方は降順に並べる。あとは尺取り法の要領で進めていく。
実装のポイント
「価値の合計の 最大値 」を入れないといけないことに注意する。
データセット 2
$DP[i][j] = i - 1$ 番目の品まで使って重さ $j$ の荷物を作るときの価値の最大値。ただし重さ $j$ を作れない場合は $-1$ である。
と定める。 $H = \min(W, 200001)$ と定める。初期状態： $DP[0][0] = 0$ 、 $DP[i][j] = -1$ 。答え： $\max _ {0 \leq i \leq H} DP[N][i]$ 。遷移は以下の通り。 $i \in N$ に対し、 $j = 0, \dots, H$ に対し、
\[
\begin{align}
DP[i + 1][j] &\gets \max(DP[i + 1][j], DP[i][j]), \\
DP[i + 1][j + w[i]] &\gets \max(DP[i + 1][j + w[i]], DP[i][j] + v[i]) & (j + w[i] \leq H).
\end{align}
\]
実装のポイント
まず $H$ の定義である。最後の答えを出すところでは、必要になる。あとは配る DP なので、 $DP[i][j] = -1$ の際は continue; をする。
データセット 3
$DP[i][j] = i - 1$ 番目の品まで使って価値 $j$ の荷物を作るときの重さの最小値。ただし価値 $j$ を作れない場合は $\infty = 10 ^ {18}$ である。
と定める。 $H = 200001$ と定める。初期状態： $DP[0][0] = 0$ 、 $DP[i][j] = \infty$ 。答えは $\mathop{\mathrm{argmax}} _ {DP[N][i] \leq W} i$ 。遷移は以下の通り。 $i \in N$ に対し、 $j = 0, \dots, H$ に対し、
\[
\begin{align}
DP[i + 1][j] &\gets \min(DP[i + 1][j], DP[i][j]), \\
DP[i + 1][j + v[i]] &\gets \min(DP[i + 1][j + v[i]], DP[i][j] + w[i]) & (j + v[i] \leq H).
\end{align}
\]
実装のポイント
上の実装ができていればこちらで気をつけることは特にないのでは。
ポイント
疲れた。 3 問分解いた。
Others
D - sample: 4, tle: 2.000, time: 59:43, from_submit: 00:00
途中で休憩を挟んだ。