2009 JOI 予選 6 ビンゴ

2018-03-22 17:35

JOI

dp

問題名

ビンゴ

方針

長さn^2の増加部分列の個数を求める問題。ただし、1≦ai≦m, sum{ai}=s, aiはdistinctという条件のもとで。

dp[i][j][k]:=数字iまでで考えて、j項目まで埋まっていて、和がkであるような通り数

初期条件：dp[0][0][0]=1, 他は0

求めるもの：dp[m][n^2][s]

遷移：

数字iを使わない：dp[i][j][k]+=dp[i-1][j][k] （数列は伸びない）
数字iを使う：dp[i][j][i+k]+=dp[i-1][j-1]k

とすると、MLEになったので、iの分の次元を削るためにswapテク（偶奇のテク）か、jのループを逆にするテクを使うといい。

解答

swap : https://joi2009yo.contest.atcoder.jp/submissions/2243605

逆向きのループ : https://joi2009yo.contest.atcoder.jp/submissions/2243509

感想

他の人の解答を見て考えたけど、しっくりきてない……。