TopCoder SRM 592 Div1 Medium
問題
二つの長さnの順列A, Bに対してmagic(A, B)を、
max(A[0], B[0]) + max(A[1], B[1]) + … + max(A[n-1], B[n-1])と定義する。
magic(A, B)がk以上になるような長さnの順列A, Bは何通りあるか、求めよ。
制約条件
n≦50
k≦2500
方針
Aを0, 1, 2, ..., n-1に固定するDPは上手くいかない。
A[i] < B[i]となるiを決めていくDPだと、今まで超えた分の状態を持たないといけなくて破綻する。
上手くいくのは、nから順にA, Bの中でどこに登場するかを決めていくDP.
a.b..
.ab..
という感じで今まで埋めたとき、次にxを置くことを考える。
大きい順に埋めているので、aとxがペアになってもmagicの値は変化しない。
今まで使った数、A, B両方で埋まっているiの個数、今までの和を状態とすれば、
遷移も、A, B両方で埋まっているiの数が増えるか、減るか、そのままかだけになって、
時間計算量O(n^2 * k)で計算できる。
ソースコード
const int mod = (int)1e9 + 7; int dp[51][51][2501]; class LittleElephantAndPermutationDiv1 { public: int getNumber(int N, int K) { memset(dp, 0, sizeof(dp)); dp[N][0][0] = 1; for(int i = N; i > 0; i--) rep(j, N + 1) rep(k, 2501){ int &cur = dp[i][j][k]; if(cur == 0) continue; //差そのまま if(i - j > 0){ (dp[i - 1][j][k + i] += cur * (ll)(i - j) % mod) %= mod; (dp[i - 1][j][k + i] += cur * 2ll * j * (i - j) % mod) %= mod; } //差増える if(i - j > 1) (dp[i - 1][j + 1][k + 2 * i] += (ll)cur * (i - j) * (i - j - 1) % mod) %= mod; //差減る if(j > 0) (dp[i - 1][j - 1][k] += (ll)cur * j * j % mod) %= mod; } ll ans = 0; rep(i, 2501) if(i >= K) ans += dp[0][0][i]; return ans % mod; } };