hogecoder

tsutaj 競技プログラミングの記録

AtCoder Grand Contest 030 F: Permutation and Minimum

問題概要

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

解説

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

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

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

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

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

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

 \mathrm{dp}[i][j][k] :=  i 番目の要素まで見て、 A で登場せずに  B でも登場しない要素でペアになっていないものが  j 個、 A で登場せずに  B で登場する要素でペアになっていないものが  k 個あるときの場合の数

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

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

ソースコード

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;
}

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