http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_e
赤のボールがA,青のボールがB個の状態から選ぶ方法の数を再帰的に求めます。これを(A, B)と定義しておきましょう。
赤を選ぶ場合単に(A-1,B)とすればいいです。青を選ぶ場合t=B+1にします。そうするとボールの数がt個になるまで赤と青のボールを好きなように選べます。それで赤がp個、青がq個(p+q=t+1)になったとしましょう。赤を使った場合は(p-1,q)、青を使った場合はs=q+1としてまたボールがq+1個になるまで好きなように選べます。q+1個になったらあとは赤を全部取ってから青をとるしかないです。なのでp,qをすべて試して(p,q)と(t+1,Bからp,qへの経路数)の積の和を求めればいいです。後者は単なるコンビネーションで、前者はdpで前処理計算できます。
区間の変な問題に言い換えてしまい惨敗でした。コンビネーションがたくさん出そうだということはわかったのですが、経路数に言い換えることはできませんでした。方針の変更は難しい。
あと再帰的に考えることの重要性も学びました。自分はdpを配る形でよく書くので再帰的に処理していることを忘れがちです。
いい言い換え+再帰的思考ができれば解けた問題でした。
int A, B; ll C[2020][2020]; ll CS[2020][2020]; ll dp[2020][2020]; void C_init(int n) { n++; rep(i, 0, n) C[i][0] = 1; rep(i, 1, n) { rep(j, 1, i + 1) { C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; C[i][j] %= mod; } } } void solve() { cin >> A >> B; C_init(2010); rep(i, 0, 2010) { rep(j, 0, 2010) { CS[i][j + 1] = CS[i][j] + C[i][j]; CS[i][j + 1] %= mod; } } rep(i, 0, A + 1) dp[i][0] = 1; rep(j, 0, B + 1) dp[0][j] = 1; rep(i, 1, A + 1) { rep(j, 1, B + 1) { dp[i][j] = (dp[i - 1][j] + CS[j - 1][min(i, j - 1) + 1]) % mod; } } ll res = 0; rep(i, 0, A + 1) { rep(j, 0, B) { if(i + j > A) continue; res += dp[i][j] * C[B - 1][j]; res %= mod; } } cout << res << "\n"; }