AtCoder Grand Contest 030 F: Permutation and Minimum

問題概要

日本語があるので原文参照 → F - Permutation and Minimum

解説

と の順序は答えにあまり関係ないので、数列を 2 個のブロックに区切って考えていき、ブロックの中は (左の値) < (右の値) という関係が常に成り立つものとする。ブロックの状態としてありえるものは以下の 3 通りである。

• 2 つとも値が確定している (入力の段階で の値がどうなるか分かる)
• 1 つだけ値が確定している
• なにも値が確定していない

今回はブロック内の値の最小値が数列 の値となるので、値の大きいものから確定させていく (値が 2 個未満入っているブロックに対して値を追加) ことを考える。動的計画法で処理しよう。

ここで、はじめに与えられる数列 で登場しなかった要素 それぞれについて、最後に生成される に登場するかどうかで場合分けして考える。

• で登場しない場合
  • は、 で登場しなかった で登場した 未満の要素とペアを組むか、 で登場してなおかつ 1 つだけ値が確定しているブロックに属している 未満の要素とペアを組む可能性がある
• で登場する場合
  • は、 で登場しなかった で登場しない を超える要素とペアを組むか、 で登場してなおかつ 1 つだけ値が確定しているブロックに属している を超える要素とペアを組む可能性がある

で登場しなかった要素が で登場するかしないかを分けて考えることで、

番目の要素まで見て、 で登場せずに でも登場しない要素でペアになっていないものが 個、 で登場せずに で登場する要素でペアになっていないものが 個あるときの場合の数

という DP を考えることができる。

下で書いたソースコードでは、 で登場しない要素同士のペアの順序を考慮していないため、最後に階乗で掛けている。

ソースコード

using mint = ModInt<MOD>;
mint dp[2][310][310];
signed main() {
    int N, M; cin >> N; M = N; N *= 2;
    int both_neg = 0;
    
    vector<int> tp(N + 1);
    for(int i=0; i<N/2; i++) {
        int a, b; cin >> a >> b;
        if(a > b) swap(a, b);

        if(b == -1) both_neg++;
        else if(a == -1 and b != -1) tp[b] = 1;
        else tp[a] = tp[b] = 2;
    }

    dp[0][0][0] = mint(1);
    for(int i=N; i>=1; i--) {
        int cur = i % 2, nxt = 1 - cur;
        for(int j=0; j<=M; j++) {
            for(int k=0; k<=M; k++) {
                if(dp[cur][j][k] == mint(0)) continue;
                if(tp[i] == 2) {
                    dp[nxt][j][k] += dp[cur][j][k];
                }
                // k 増えるのここだけ → 3 次元目は (-1, 値入っているもの) のペア
                if(tp[i] == 1) {
                    dp[nxt][j][k+1] += dp[cur][j][k];
                    if(j) dp[nxt][j-1][k] += dp[cur][j][k];
                }
                // j 増えるのここだけ → 2 次元目は (-1, -1) のペア 
                if(tp[i] == 0) {
                    dp[nxt][j+1][k] += dp[cur][j][k];
                    if(j) dp[nxt][j-1][k] += dp[cur][j][k];
                    if(k) dp[nxt][j][k-1] += dp[cur][j][k] * mint(k);
                }
                dp[cur][j][k] = mint(0);
            }
        }
    }

    mint ans = dp[0][0][0];
    while(both_neg) ans *= mint(both_neg--);
    cout << ans << endl;
    return 0;
}

説明がかなり難しいですね・・・。これ自力で解きたかったなぁ