https://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_f
解説と完全に同じことしたけどそれでも結構バグらせた。
頑張って問題を変形していくと、解説の2つめの四角で囲ってあるような問題に落とし込めます。
ここからが難しくて、ctがどのような条件を満たすか考えていきます。
作業を後ろからみると(ここが思いつかない)ctはa(t+1),b(t+1),c(t+1)以降に含まれず、かつ(a0,a1,...,at,b0,b1,...,bt)に含まれない要素になります。この数をf(it, jt, t)とすると、求めるのはΠf(it,jt,t)の和です。ここでdp(i,j,t):=(it'=i,jt'=jの時のΠ(1,..,t')f(it,jt,t))の和と定義すると、
dp(i,j,t)=f(i,j,t)*Σ(x < i,j < y)dp(x,y,t-1)となるので遷移がいい感じにまとめられてO(N^3)になります。
後ろから見る考え方はよくあるけどこういう複雑な問題でなかなか使えないですね。
あとctというある要素1つだけに注目して考えるというのも大事です。
この問題からわかるように、DPの計算量を落とすときは、簡単な数式の形に変形して遷移をじっくり見ることが重要になりそうです。そうするとsegtreeに落とし込めたり、累積和が使えたりします。
int N, n; ll dp[400][400][134]; bool circ[400][400][400]; int cnt[410][410]; int A[410], B[410]; int f(int i, int j, int t) { return max(N - 3 * (n - t) - cnt[i][j], 0); } void solve() { cin >> N; n = N / 3; rep(i, 0, N) { cin >> A[i]; A[i]--; } rep(i, 0, N) { cin >> B[i]; B[i]--; } if(A[0] == B[0]) { cout << "0\n"; return; } rep(i, 0, N + 1) { rep(j, 0, N + 1) { if(j - 1 >= 0) { rep(k, 0, N) circ[i][j][k] = circ[i][j - 1][k]; circ[i][j][B[j - 1]] = 1; } else if(i - 1 >= 0) { rep(k, 0, N) circ[i][j][k] = circ[i - 1][j][k]; circ[i][j][A[i - 1]] = 1; } cnt[i][j] = accumulate(circ[i][j], circ[i][j] + N, 0); } } rep(i, 0, N) { dp[i][0][1] = 1; dp[0][i][1] = 1; } rep(i, 1, N) { rep(j, 1, N) { rep(k, 1, n + 1) { if(!circ[i][j][A[i]] && !circ[i][j][B[j]] && A[i] != B[j]) { dp[i][j][k] = dp[i - 1][j - 1][k - 1] * f(i + 1, j + 1, k) % mod; } ADD(dp[i][j][k], (dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k] + mod) % mod); } } } ll res = dp[N - 1][N - 1][n]; rep(i, 0, n) { MUL(res, (N - i * 3 - 1) * (N - i * 3 - 2) % mod); } cout << res << "\n"; }
MLEしまくった…。