迷いませんか?

継続しないを座右の銘に

AGC 030 F - Permutation and Minimum

AGC 030 F - Permutation and Minimum

初めて1600点とかいう高得点の問題をACできたので嬉しくてブログを書く

問題概要

いくつかの要素が欠けている1〜2Nで構成された順列Aが与えられるので,欠けている部分を埋めて順列A'を作る.
 {min(A'[2i], A'[2i+1])}をB[i]とした数列Bを構成する.
このときBとなる数列は何種類できるか.

解法

なんか解説の解法はめっちゃ簡潔でした,僕の解法は簡潔ではありません(はい)
解説「2N→1の順に見ていきます」
ぼく「1→2Nの順に見ていきます(不穏)」

どう考えてもDPっぽいので,DPとしてどういう情報を持ちたいかを考えます
A[2i]とA[2i+1]をペアにして考えるべきだとわかるので
1. どちらもまだ決まっていないペアの数 2. 片方がaだと決まっていて,今見ている数xよりも大きいようなペアの数 3. 片方がaだと決まっていて,今見ている数xよりも小さいようなペアの数 4. どちらも決まっているペアの数

の4種類の情報がほしいことがわかります
ここで,ペアの総数,既にいくつ決まっているかがわかると4種類のうち,種類1か4の片方,種類2か3の片方が決まっていれば残りもわかるので,2種類だけ持てばいいことがわかります
これはよくある次元を減らすテクなのでここまでは自明です

今回はdp[i][j][k] := 現在iを見ていて,種類1のペアがj個,種類2のペアがk個として考えます.
Nがペアの総数,Mが既に決まっている要素数,種類3の数をk3, 種類4の数をk4とすると,  {k3+2*k4 = M-k,k3+k4 = N-j-k} の2式が立つので  {k3 = 2*N-M-2*j-k, k4 = M-N+j} となる

そして小さい方から見ていくとき,その数がAの中に含まれているときと含まれていないときを分けて考えます.

Aに含まれていないとき

このとき,iは種類1,種類2,種類3のペアのうちのどれに含めるかの選択肢があります.
ただし,種類3に含めるときは結果となるBに変化が起こらないため足し込むときに係数は1で,それ以外のときはBに影響するので係数はそのペアの数になります
種類1のペアに含めると,次のi+1を見るときのことを考えると種類3が増えますが,dp配列の添字には含まれないので種類1だけ減らします
同様に種類2だと種類4が増えますが種類4は添字にないので種類2だけ減らし,種類3のとき種類3が減って種類4が増えますがどちらもないので何もしません

if (j > 0) dp[i+1][j-1][k] += dp[i][j][k] * j;
if (k > 0) dp[i+1][j][k-1] += dp[i][j][k] * k;
if (k3 > 0) dp[i+1][j][k] += dp[i][j][k];

Aに含まれているとき

iのペアがAで決まっているときは最初から種類4の個数としてカウントされているので添字部分では何も変化しません.

iのペアがAで決まっていないとき,最初は種類2としてカウントされていますが,i-1までの間に種類4になっている可能性があります
つまり,dp[i][j][k]で,k個の中に含まれている場合と既に含まれていない場合があるので,含まれている場合はdp[i+1][j][k-1]に遷移してあげないといけません.

Aで,一方がi以上でもう一方が決まっていないようなペアの数をpとしておくと,p個のうちk個が残っているということになります(新たに増えた一方のみが決まっていないようなペアは種類3でありkにカウントされないので)
iのペアが既に決まっている場合の数は,p個のペアについて均等になっているはずなので,dp[i][j][k] * k / pとなります.
まだ決まっていないときは種類2としてカウントされてた分が種類3になるので種類2が一つ減るように遷移をします
よって遷移は次のようになります

if (k > 0) dp[i+1][j][k-1] += dp[i][j][k] * (p - k) / p;
dp[i+1][j][k] += dp[i][j][k] * k / p;

pは最初に累積和をしておくと簡単に求められます

ここまでをやると計算量はそのままO(N3)になります
beetさんから指摘されましたがModの割り算をしているのでlog MODがかかり,O(N3 log MOD)です

コードは下のようになりますが,変数名とか無駄な変数とか変なところがたくさんあるので参考にはなりません

int main(void) {
    int N;
    cin >> N;
    vector<int64> A(2*N), sc1(2*N+1, 0);
    vector<bool> used(2*N+1, 0), ispair(2*N+1, 0);
    int cnt[3] = {};
    int luz = 0;
    REP(i, 2*N) {
        cin >> A[i];
        if (A[i] != -1) used[A[i]-1] = 1;
        if (A[i] != -1) luz += 1;
        if (i%2) {
            cnt[(A[i-1] != -1) + (A[i] != -1)]++;
            if ((A[i-1] != -1) + (A[i] != -1) == 1) {
                sc1[max(A[i-1], A[i])]++;
            } else if ((A[i-1] != -1) + (A[i]!=-1) == 2) {
                ispair[A[i-1]-1] = 1;
                ispair[A[i]-1] = 1;
            }
        }
    }
    REP(i, 2*N) sc1[i+1] += sc1[i];
    vector<vector<Mint>> dp(310, vector<Mint>(310, 0));
    dp[cnt[0]][cnt[1]] = Mint(1);
    REP(i, 2*N) {
        vector<vector<Mint>> dp2(310, vector<Mint>(310, 0));
        REP(j, N+1) { // [-, -] のかず
            REP(k, N+1) { // [-, *]かつ*>iの数
                int64 rest = N-j-k;
                int64 latte = luz-N+j; // [*, *]
                int64 beet = 2*N-luz-2*j-k; // [-, *]かつ*<i
                if (j < 0 || k < 0 || rest < 0 || latte < 0 || beet <0) continue;
                if (used[i]) {
                    if (ispair[i]) {
                        dp2[j][k] += dp[j][k];
                    } else {
                        Mint exist_posi = Mint(k)/Mint(sc1[2*N]-sc1[i]), inv_posi = Mint(sc1[2*N]-sc1[i]-k)/Mint(sc1[2*N]-sc1[i]);
                        if (k > 0)
                            dp2[j][k-1] += dp[j][k] * exist_posi;
                        dp2[j][k] += dp[j][k] * inv_posi;
                    }
                } else {
                    if (j > 0)
                        dp2[j-1][k] += dp[j][k] * j;
                    if (k > 0)
                        dp2[j][k-1] += dp[j][k] * k;
                    if (beet > 0)
                        dp2[j][k] += dp[j][k];
                }
            }
        }
        if (!used[i]) luz++;
        swap(dp, dp2);
    }
    cout << dp[0][0] << endl;
}