TopCoder SRM592: LittleElephantAndPermutationDiv1

LittleElephantAndPermutationDiv2 のように片方を(1,...N) に固定して考えるとその時点で解けなくなる。むずかしい。

a1 , .. , an
b1 , .. , bn

順列 a,b に対して、N から 1 の順、つまり大きいものから配置していくことを考える。
大きい順に配置するため、両方空いている場所に値 i を配置した時点で もう片側に i 以下の値しか入らないので、 magic(A,B) に i が追加される。

値の配置パターンを大きく以下の４通り。

「a,b 両方空いている場所」を２つ選んで値を配置

_ .... _  ->  N .... _
_ .... _  ->  _ .... N

上述の通り、空いている片側にはそれ以下の値しか入らないので、この時点で magic(A,B) に 2 * N 増える。
そして「a だけ空いている箇所」と「b だけ空いている箇所」が１つずつ増える

「a,b 両方空いている場所」を１つ選んで値を配置

_ ...  ->  N ....
_ ...  ->  N ....

magic(A,B) は N 増える。
「a だけ空いている箇所」と「b だけ空いている箇所」は特に変わらない

片方が空の場所と、両方とも空の場所を選んで配置

_ ... _  ->  N ... _
X ... _  ->  X ... N

すでに埋まっている値 X はより大きい値なので、magic(A,B) は N だけ増える。
「a だけ空いている箇所」と「b だけ空いている箇所」は特に変わらない

それぞれ片方が空の場所を選んで配置

_ ... X  ->  N ... X
X ... _  ->  X ... N

この場合は、magic(A,B) は増えない。
「a だけ空いている箇所」と「b だけ空いている箇所」は１ずつ減る。

ここで「a だけ空いている箇所」と「b だけ空いている箇所」の個数は同じになるので、後は
「何個配置したか」「a だけ空いている箇所」「magic(A,B)の値」で動的計画法を適用すればよい。

public class LittleElephantAndPermutationDiv1 {
    int mod = 1000000007;

    int?[, ,] memo = new int?[55, 2502, 55];

    int dfs(int N, int K, long single) {
        if (K < 0) K = 0;
        if (N == 0) {
            return K == 0 && single == 0 ? 1 : 0;
        }
        if (!memo[N, K, single].HasValue) {
            long val = 0;

            long empty = N - single;
            // 両方とも空いている場所を２つ選んで N を配置
            // _ .... _  ->  N .... _
            // _ .... _  ->  _ .... N
            if (empty >= 2) {
                val += empty * (empty - 1) * dfs(N - 1, K - 2 * N, single + 1);
            }

            // 両方とも空いている場所に１つ選んで N を配置
            // _ ...  ->  N ....
            // _ ...  ->  N ....
            if (empty >= 1) {
                val += empty * dfs(N - 1, K - N, single);
            }

            // 片方が空の場所と、両方とも空の場所を選んで配置
            // _ ... _  ->  N ... _
            // X ... _  ->  X ... N
            if (empty >= 1 && single >= 1) {
                val += empty * single * dfs(N - 1, K - N, single) * 2;
            }

            // それぞれ片方が空の場所を選んで配置
            // _ ... X  ->  N ... X
            // X ... _  ->  X ... N
            if (single >= 1) {
                val += single * single * dfs(N - 1, K, single - 1);
            }

            memo[N, K, single] = (int)(val % mod);
        }
        return memo[N, K, single].Value;
    }

    public int getNumber(int N, int K) {
        return dfs(N, K, 0);
    }
}