E 問題「はじめての動的計画法」解説
部分点（2 点）解法
2 点分の部分点では $x \leqq 1000$ が成立する.
元の問題の制約からおける荷物の数 $N$ は 1000 以下である. よって, $x > 1$ であれば, たとえば重さが $W$ である荷物を $x - 1$ 個出力すれば重さ $W$ 以下の荷物の集合はちょうど $x$ 個できる.
注意すべき入力として, $x = 1$ のケースがある. 元の問題の性質から, 空集合は必ず重さの和が $W$ 以下の集合を成すことになることと, $N \geqq 1$ であることに気をつけねばならない. この場合はたとえば $N = 1,\ W = 1,\ a_1 = 2$ などの入力が正答となる.
満点解法
満点の制約では $x \leqq 10^{18}$ となり, 先の部分点の様に 1 つの荷物で 1 つの条件を満たす集合を成していては 1000 個以内の荷物で多くの組み合わせを作り出すことが出来ない.
ここでは具体的に $10^{18}$ 以下の任意の組み合わせを作る方法を紹介する. ただし $x = 1$ のときは 2 点解法の様に場合分けをする必要がある.
アルゴリズム
まず, $W = 1000$ として固定する.
問題の性質から, この状況で重さの和が $1$ の荷物が $M$ 個あれば, それらから荷物を作る組み合わせは $2^M$ 個あることになる.
$10^{18} < 2^{60}$ であるから, たかだか 60 個以内の 1 があれば $x$ 個以上の条件を満たす荷物の集合が出来る事になる. しかし, これでは $x$ が 2 の冪以外のときに正答を導けない. そこで, 次の事実を使う.
- 用いる荷物の中に $m(\leqq 60)$ 個重さ $1$ の物があるとする. この時, 重さ $W - k (0 \leqq k \leqq m)$ の荷物を追加すると, 条件を満たす集合の個数が $\displaystyle \sum_{i = 0}^{k} {_m}C_i$ 個増加する.
重さが $1$ でない全ての荷物 $a_i$ について $a_i > \dfrac{W}{2}$ であれば他の重さ $1$ 以外の荷物から組み合わせの個数の影響を受けない. よって, それぞれの $a_i$ について, $m$ 個ある重さ $1$ の荷物を $1000 - a_i$ 個以下選ぶ組み合わせの数が加算される.
よって, 次のようにするとちょうど重さの和が $W$ 以下の荷物の集合の個数が $x$ 個となる.
- $[\log_2 x]$ 個の $1$ を出力する. ただし $[x]$ は $x$ の整数部分を表すとする.
- $k = \dfrac{[\log_2 x]}{2}$ として, $y = x - 2^{[\log_2 x]}$ とする.
- $k < 0$ となるまで以下を繰り返す.
- $\left[\dfrac{y}{\sum_{i = 0}^{k}{_m} C _i}\right]$ 個 $1000 - k$ を出力し, 出力した個数だけ $y$ から $\displaystyle \sum_{i = 0}^{k} {_m}C_i$ を引く.
- $k$ を 1 減らす.
$k = 0$ であれば $\displaystyle \sum_{i = 0}^{k}{_m} C _i = 1$ であるから, このアルゴリズムを用いることで $x$ 個の重さが $W$ 以下の集合を作ることが可能である.
荷物の個数の上界の評価
一見しただけでは, 上述のアルゴリズムで本当に 1000 個以下の荷物で $10^{18}$ 以下の集合の組み合わせが出来るのかが分からない. そこで, 次のように上界を評価する.
以下では簡潔に式を書くために $\displaystyle \sum_{i = 0}^{k} {_m} C _i$ を $_m S _k$ と表記する.
このアルゴリズムでは, $X$ 個の重さ $1$ の荷物を使うことで表現しようとする通り数の最大値は $2^{X + 1} - 1$ である. よって $1 \leqq X \leqq 60$ に対して, $X$ 個の 1 を使うときの荷物の個数の上界は,
$$ ubound(X) = X + \dfrac{2^{X} - 1}{_X S _{[\frac{X}{2}]}} + \sum_{i = 0}^{[\frac{X}{2}] - 1}\left[\dfrac{_X S _{i + 1} - 1}{_X S _i}\right] $$
となる. 後半の和は, 上述のアルゴリズムでの割られる数を最大にしたものを足しあわせている.
簡単なプログラムを書くと $ubound(X)$ は単調に増加し, $X = 60$ では $ubound(X) = 265$ であることが分かる.
よって, $x \leqq 2^{X}$ であれば $O(ubound(X))$ 個の荷物で $x$ 個, 重みの和が $W$ 以下の集合をちょうど作ることができることが分かる.
このアルゴリズムは出力する荷物の個数に比例する時間の計算と, 二項係数の計算が必要になるため, $O(ubound(X) + X^2)$ 時間でこの問題を解くことが出来る.