Official

D - Strange Lunchbox Editorial by leaf1415


高橋君が \(i = 1, 2, \ldots, N\) の順番で「 \(i\) 種類目の弁当を買うか買わないか」を決定していくとします。
高橋君は、\(X\)以上のたこ焼きと \(Y\)以上のたい焼きを食べられれば満足できるので、 高橋君が買い物の途中で \(X\) 個より多くのたこ焼き(または \(Y\) 個より多くのたい焼き)を手に入れたときには、超過した分のたこ焼き(またはたい焼き)を即座に青木君にあげることにします。

動的計画法で本問題を解きます。

下記をすべて満たす状態を状態 \((i, j, k)\) と呼ぶことにします。

  • 高橋君が \(1, 2, \ldots, i\) 種類目の弁当について買うかどうかをすでに決定している。
  • 高橋君がそれまでに手に入れたたこ焼きの個数は \(j\)
  • 高橋君がそれまでに手に入れたたい焼きの個数は \(k\)

高橋君が買い物を始める前の初期状態は状態 \((0, 0, 0)\) です。
高橋君は、\(N\) 種類の弁当それぞれについて買うか買わないかを決定した後の時点で、\(X\) 個のたこ焼きと \(Y\) 個のたい焼きを手に入れているようにしたいので、高橋君が目指す状態は状態 \((N, X, Y)\) です。 ( \(X\) 個より多くのたこ焼き(または \(Y\) 個より多くのたい焼き)を手に入れたときには、超過分を青木君にあげることに注意して下さい。)
よって本問題は、状態 \((0, 0, 0)\) から開始して状態 \((N, X, Y)\) に到達するまでに買う弁当の個数の最小値を求める問題です。

\(0 \leq i \leq N, 0 \leq j \leq X, 0 \leq k \leq Y\) について \(\mathrm{dp}[i][j][k]\) を下記の通りに定めます。

\(\mathrm{dp}[i][j][k] := \)(状態 \((i, j, k)\) に達するまでに、高橋君が購入する弁当の個数の最小値)

ただし、状態 \((i, j, k)\) に到達し得ない場合は \(\mathrm{dp}[i][j][k] = \infty\) とします。

このとき、本問題の答えは \(\mathrm{dp}[N][X][Y]\) となります。 ただし、\(\mathrm{dp}[N][X][Y] = \infty\)のときは、高橋君は \(X\) 個以上のたこ焼きと \(Y\) 個以上のたい焼きを手に入れられないため、\(-1\) を出力します。

この \(\mathrm{dp}[N][X][Y]\) を求める方法を以下で述べます。

まず、すべての \(0 \leq i \leq N, 0 \leq j \leq X, 0 \leq k \leq Y\) について \(\mathrm{dp}[i][j][k] \leftarrow \infty\) と初期化します。
そして、\(i = 0, 1, 2, \ldots, N\) の順番に、\(\mathrm{dp}[i][\ast][\ast]\) の正しい値を、以下のように求めていきます

(a) \(i = 0\) のとき

\(i = 0\) のとき、状態 \((0, 0, 0)\) のみが起こり得ます。 状態 \((0, 0, 0)\) に達するまでに購入する弁当の個数は明らかに \(0\) 個です。 よって、\(\mathrm{dp}[0][0][0] \leftarrow 0\) と更新し、\((j, k) \neq (0, 0)\) については \(\mathrm{dp}[0][j][k] = \infty\) のままにしておきます。

(b) \(i \geq 1\) のとき

\(\mathrm{dp}[0][\ast][\ast], \mathrm{dp}[1][\ast][\ast], \ldots, \mathrm{dp}[i-1][\ast][\ast]\) の正しい値が計算されているとき、\(\mathrm{dp}[i][\ast][\ast]\) の正しい値を計算する方法を述べます。

高橋君が状態 \((i-1, j, k)\) にあるとき、高橋君は \(i\) 種類目の弁当を買うか買わないかのどちらかの選択ができます。

  • 高橋君が \(i\) 種類目の弁当を買う場合、\(A_i\) 個のたこ焼きと \(B_i\) 個のたい焼きが新たに手に入る( \(X\) 個を超えるたこ焼き、\(Y\) 個を超えるたい焼きは青木君にあげる)ので、状態は \((i, \min(j+A_i, X), \min(k + B_i, Y))\) に変わり、購入した弁当の個数が \(1\) 増えます。
  • 高橋君が \(i\) 種類目の弁当を買わない場合、状態は \((i, j, k)\) に変わり、購入した弁当の個数は増えません。

上記 の \(2\) つの選択に対応して、下記の \(2\) つの更新を行います。

\(\mathrm{dp}[i][\min(j+A_i, X)][\min(k+B_i, Y)] \leftarrow \min(\mathrm{dp}[i][\min(j+A_i, X)][\min(k+B_i, Y)], \mathrm{dp}[i-1][j][k] + 1)\)

\(\mathrm{dp}[i][j][k] \leftarrow \min(\mathrm{dp}[i][j][k], \mathrm{dp}[i-1][j][k])\)

以上に述べた方法で、すべての \(0 \leq i \leq N, 0 \leq j \leq X, 0 \leq k \leq Y\) について \(\mathrm{dp}[i][j][k]\) の正しい値を計算できるため、そのうち \(\mathrm{dp}[N][X][Y]\) の値(または \(-1\) )を出力すれば良いです。
このアルゴリズムの時間計算量は \(\mathrm{O}(NXY)\) です。

posted:
last update: