CPSCO2019 Session3: F - Flexible Permutation

問題記録 CPSCO2019 DP 順列のDP

https://atcoder.jp/contests/cpsco2019-s3/tasks/cpsco2019_s3_f

問題概要

１～Nの順列Pのうち

  • Pi > i であるような i がA個
  • Pi < i であるような i がB個
  • Pi = i であるような i がN - A - B個

という条件をすべて満たすものが何通りあるか求めよ。

N <= 300

解法

O(N3)解

想定解はO(N3)で、これはwriterによる解説がわかりやすいのでそちらを見るのが早い。ざっくり言うと (1～iを1～Piのどこかに置いた、>がa個、<がb個) を状態にとるDPで、(i+1)への遷移ではまず(i+1)をP(i+1)に置いてから既に置いてある数のうちどれかひとつと位置を入れ替える（もしくは入れ替えを行わない）ことを考える。数を小さい順に見ていっていることからP(i+1)に置かれる数は必ず < になるし、手前に置かれることになる(i+1)は必ず > になる。なので考慮すべき遷移は「> と入れ替える」「< と入れ替える」「入れ替えない」の3通りのみとなり、O(1)で計算できる。よって状態O(N3), 遷移O(1)の全体O(N3)で答えが出る。

O(N2)解

先程の解説でも言及されている通りこの問題にはO(N2)解が存在する。O(N3)解では = の数も考慮するためにO(N3)となっているが、これを捨てることで高速化できる。まず = にする(N-A-B)個の場所を先に決め打ってしまうと、あとは(A+B)要素の順列において「>がA個」「<がB個」「=が0個」の数をかぞえる問題になる（最初に決め打った分は最後にnC(n-a-b)をかければよい）。

DP自体も基本的にはO(N3)版と同じようなことをする。ただし=を捨てたので状態は (1～iを1～Piのどこかに置いた、>がa個) のN2に落ちる。また=が0個なので遷移の際に「入れ替えない」という選択肢はない。ただしどうしても=の存在する状態を経由しないと生み出せない順列があり（例えば2143は213からでないと作れない）、その分を考慮する必要がある。そしてこのようなケースは新たな数を一度に2つ追加してやることでうまく拾うことができる。つまり=がひとつもない状態の中のどこかにひとつ=を生やして、それを(i+2)と入れ替えることにする、という方法である。これは i -> (i+2) への遷移になる。またどの位置を=にするかで (i+1) の自由度があるのでその分を掛けるようにする。

感想

O(N2)でだいぶ悩んだ　説明できている気がしない

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto A = s[1];
    auto B = s[2];

    if (A == 0 && B == 0) {
        writeln(1);
        return;
    }
    
    if (A == 0 || B == 0) {
        writeln(0);
        return;
    }

    auto dp = new long[][](A+B+1, A+B+1);
    dp[2][1] = 1;

    foreach (i; 2..A+B) {
        foreach (j; 0..i+1) {
            (dp[i+1][j] += dp[i][j] * j % MOD) %= MOD;
            (dp[i+1][j+1] += dp[i][j] * (i - j) % MOD) %= MOD;
            if (i + 2 <= A + B) {
                (dp[i+2][j+1] += dp[i][j] * (i + 1) % MOD) %= MOD;
            }
        }
    }
    
    writeln( comb(N, A+B) * dp[A+B][A] % MOD );
}

long f(int n) {
    long ret = 1;
    foreach (i; 1..n+1) ret = ret * i % MOD;
    return ret;
}

long comb(int n, int r) {
    return f(n) * powmod(f(n-r), MOD-2, MOD) % MOD * powmod(f(r), MOD-2, MOD) % MOD;
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}