2009 JOI 予選6 ビンゴ
2009 JOI 予選6 ビンゴ についての記事です．
問題へのリンク (AtCoder)
上のリンクで問題は見られますが，要は，$n$, $m $, $s$ が与えられた時， 以下を満たす数列 $\{a_i\}_i $ の個数を求めよ，というものです． 制約は，$1 \leq n \leq 7$, $1 \leq m \leq 2000$, $1 \leq s \leq 3000$．
- 長さは $n*n$
- 和は $s$
- 各 $a_i$ は1以上 $m $ 以下の整数
- 狭義単調増加
経緯
JOIの問題も解くと良いよ．というお勧めがあちこちで見られるので，ときどきは解いてみようと思い，この問題を考えました．
一応DPで解けまして，実行時間は 2500ms くらいでした．(制限時間は10秒と書いてあります．) ところが，「すべての提出」をみると，数ms で終了するコードがACしています．読んだらとても賢いコードだったので， メモしておきます．
自分の解法
$dp[i][v][w]$ = 長さが $i$ で，和にあと $v$ の余裕があって，最終項が $w$ である数列の個数．
和の「余裕」というのは，最終項を $w$ とすると，現在までの数列の和から後少なくとも $(w + 1) + (w + 2) + \cdots (w + (n^2 - i))$ は増えることが決まっているので，その分も加えた上で，$s$ との差を取ったものです．
$(i, v, w)$ の遷移先は だいたい $v / (n^2 - i)$ 個くらいなので， 計算量は $O( \sum_{i} sm (s / i) ) = O(s^2m\log n)$． 大きいけれど，10秒なのでなんとか間に合う，という感じです．(コード)
ちなみに，メモリ制限は256MBなので，dp を全部とっておくとMLEします．
blog で見た解法
検索をしていたらもっと賢い解法が紹介されていました． リンク先を見ていただければ良いのですが，ここにも書きますと，一番外側のループを数列の長さにするのではなく， 最大値の方にするというものです．
$dp[w][i][v]$ = $1$から$w$までの数を使ってできる長さ $i$ の数列で和が $v$ であるものの個数．
こちらは，各$(w, i, v)$ の遷移先は 2 個しかないので，計算量は $O( n^2 m s)$． 実装してみる と，実行時間は 1000ms ほどでした．
速い解法
提出されていた数msで終了するコードを読んでみたところ， 次のようにできていました．
$dp[i][v]$ = 長さが $i$ で，和が $v$ である数列の個数．
一見，最大値はいらないのか?? と思うのですが，いらないようです．テーブルの更新は次のようになっています:
- $dp[i][j] = dp[i][j] + dp[i-1][j-i] + dp[i][j-i]$
- $dp[i][j] = dp[i][j] + dp[i-1][j - (m+1)]$
たとえば $i = 3$, $m = 5$ としてみましょう．dp[3,9] には，2つの数列 $2, 3, 4$ および $1, 3, 5$ が属します (面倒なので数と集合を混同しています)． これらの数列の各数から1ずつ引いた数列 (ただし 0 になったら削除する) を作ってみますと， $1, 2, 3$ および $2, 4$ となります．これらは，dp[3][6] および dp[2][6] に属します． つまり，$dp[i-1][j-i]$ と $dp[i][j-i]$ です．最初の式はこのように導出されます．
逆に，$dp[i-1][j-i]$ と $dp[i][j-i]$ に属する数列の各数 (前者は0が先行すると考える) に1を加えると $dp[i][j]$ に属する数列になるかというと，だいたいなるのですが，$m $ の制約が問題になります． たとえば，$1,5$ は dp[2][6] に属しますが，$1, 2, 6$ は，$m = 5$ なので，制約に反しています． 新たに制約に反する数列ができる場合，その数列は，最終項 (今の場合は6)が $m + 1$ で， それを除いた数列 (今の場合は $1,2$) は， $dp[i-1][j - (m + 1)]$ に属していることがわかります．これが2番目の式が必要な理由です．
これなら計算量は $O(n^2 s)$ ですから，一瞬で答が出るのももっともです． こんなのどうしたら考えられるんですかね?
