[1] 動的計画法

問題をわかりやすく言い換えましょう。各整数 \(i=1,2,\ldots,N\) について、\(B\) の中に含まれる \(i\) の個数を \(d_i\) とすると、二つの条件は以下のように書けます。

• \(d_i \leq A_i\)
• \(B\) の \(i\) 番目の位置には、\(d_j\leq A_i\) を満たすような整数 \(j\) を配置することができる

上の条件から、\(d_i\) が小さくなるほど、配置できる整数の種類も、配置できる場所も増えていくことがわかります。この考察から、\(d_i\) が大きい順に配置を決めていくような動的計画法が有効だと考えられます。

\(\mathrm{dp}[i][j][k]\) を、\(B\) での出現個数が \(i\) 個より大きいような整数の場所を決めて、決めた整数の種類数が \(j\) 個、決めた整数の個数が \(k\) 個の場合の数とします。また、\(C_j\) を、 \(A_i \geq j \) なる \(i\) の個数とします。

\(\mathrm{dp}[i][j][k]\) からの遷移を考えましょう。\(i\) 個出現する整数が \(l\) 種類だとします。

このとき、\(i\) 個出現する整数の選び方は \(\binom{C_i - j}{l}\) 通りです。次に、整数の場所の選び方は多項係数 \(\binom{C_i-k}{\underbrace{i,\ldots, i}_{l個}, C_i-k-il}\) 通りです。

結局各 \((i,j,k,l)\) に対して以下の更新を行えばよいです。

• \(\mathrm{dp}[i-1][j+l][k+il]\) に \(\displaystyle \mathrm{dp}[i][j][k] \ \binom{C_i - j}{l} \binom{C_i-k}{\underbrace{i,\ldots, i}_{l個}, C_i-k-il} \) を加算する

[2] 計算量解析

計算量を解析しましょう。一見状態が\(\mathrm{O}(N^3)\) 、遷移が \(\mathrm{O}(N)\) で \(\mathrm{O}(N^4)\)に見えるかもしれません。しかし実際は有効な範囲のみ \((i,j,k,l)\) を考えると、 \(\mathrm{O}(N^3)\) で動作します。

証明：ある \(i\) について、\(\mathrm{dp}[i][j][*][*]\) が \(0\) 以外の値を取り得るような \(j\) の範囲は\(0\leq j \leq \lfloor \frac{N}{i+1}\rfloor \) であることがわかります。さらに \(l\) の有効な範囲も、\(0\leq j \leq \lfloor \frac{N}{i}\rfloor \) であることがわかります。\(i,k\) は全ての範囲を見たとしても、遷移の回数は \(\sum_{i=1}^N N(\big\lfloor \frac{N}{i+1}\big\rfloor+1)(\big\lfloor \frac{N}{i}\big\rfloor+1)\) 回であり、展開して一番主要な部分を見ると

\[\sum_{i=1}^N N\Big\lfloor \frac{N}{i+1}\Big\rfloor\Big\lfloor \frac{N}{i}\Big\rfloor \leq N^3 \sum_{i=1}^N \frac{1}{i(i+1)}=\frac{N^4}{N+1}\]

と評価できるので、遷移回数が \(\mathrm{O}(N^3)\) であることが分かりました。

結局、\(j,l\) について有効な範囲のみを考えて [1] の動的計画法を行うことで、この問題を \(\mathrm{O}(N^3)\) で解くことができました。