Dice Sum [ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） C]

https://atcoder.jp/contests/abc248/tasks/abc248_c

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc248/submissions/31043632

この問題では動的計画法を用いて、答えを作成していく。
動的計画法の入門の次の一手くらいの問題なので、全く分からないという方は他の入門サイトで学習してくることをすすめる。

何から始めるか

とある数列の構築方法の組数を計算する問題であり、かつ、modで組み合わせ数を計算するような問題である。
このような問題の解法として動的計画法は良く使われており、既視感から動的計画法を使った解法を考え始める人も多いだろう。
実際自分はノータイムでDPを考え始めたので、この部分は経験によって埋まる部分だと思う。

動的計画法

動的計画法と言えば、

dp[i] := 数列のi番目まで確定しているときの組み合わせ

なので、これをベースに考えてみよう。
数列は1～Mの数が選択できるので、M=3であるとすると、2番目までの作り方は以下の9通りである。

1 1  
1 2  
1 3  
2 1  
2 2  
2 3  
3 1  
3 2  
3 3  

この時、dp[2] = 9のように計算することができ、dp[3]を計算するためには、3番目を1～Mで選択した場合を考えて遷移を考える。
だが、今回の問題では最終的に数列の総和について条件が課されている。
ということは数列の長さという特徴以外に、総和という特徴も考慮して分類する必要が出てくることになる。
しかも、ここで重要なのが、総和さえ求めておけば、今までどんな数列が選ばれていたかは後の選択には影響しないということである。
つまり、総和が4である「1 3」と「2 2」は数列の3番目以降を選ぶという観点では、条件が全く同じになる。
よって、特徴として総和を選ぶことで最終的な条件判定はできるまま、計算をまとめてしまうことができるようになる。
次のようなDPを考えよう。

dp[i][sum] := 数列のi番目まで確定していて、これまでの総和がsumである組み合わせ

上の例でいうと、

dp[2][2] = 1
dp[2][3] = 2
dp[2][4] = 3
dp[2][5] = 2
dp[2][6] = 1

となる。

dp[i][sum]からの遷移としては、1～Mのいずれかnxtを選ぶような遷移になり、
dp[i + 1][sum + nxt] += dp[i][sum]
という感じでやっていくと良い。ソースコードを見てもらう方が分かりやすいかもしれない
。
このように状態が2つ以上になるDPも頻繁に出てくるので、DPの雰囲気をつかんだら、このような問題にも取り組んでみてほしい。

int N, M, K;
mint dp[51][3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;

    dp[0][0] = 1;
    rep(i, 0, N) rep(sum, 0, K + 1) rep(nxt, 1, M + 1) dp[i + 1][sum + nxt] += dp[i][sum];

    mint ans = 0;
    rep(sum, N, K + 1) ans += dp[N][sum];
    cout << ans << endl;
}