SRM 673 div2 hard:BearPermutations2

問題

解法

cartesian tree で注目すべき特徴は,
・数列の最小の要素が cartesian tree の一番上に来る
・最小の要素を中心に, 数列は左側と右側に分かれる
・で, 左側と右側でまた cartesian tree が出来る

ということで, 再帰的な関係があるわけなので, これを上手く利用しましょう。

dp[n] = (長さ n の n! 通りの数列におけるスコアの合計) とします。メモ化再帰的にこの dp[n] を求めましょう。
まず, dp[0] = dp[1] = dp[2] = 0 ですね。
数列の最小の要素が何番目に来るかで場合分けをします。すると, i の左側には i 個の要素が, 右側には n-i-1 個の要素がありますね。左側の要素がどうなるかは, ${}_{n-1}C_{i-1}$ 通りの選び方があります。

右側の要素がどう並んでいるかに関係なく, 右側の要素の並びのそれぞれで左側の要素は dp[i] という合計スコアをとるので, これで dp[i]*(n-i-1)! という点数が稼げます。同様に, 左側の要素の並びそれぞれで右側の要素は dp[n-i-1] という合計スコアを取るので, dp[n-i-1]*i! という点数が稼げます。

また, i の左側にある最小要素と, i の右側にある最小要素の座標の差によってもスコアが得られます。
左側から最小要素を決めたら, 残りの左側の数は好きに並べて良いので, (i-1)! 通り, 右側も同様なので (n-i-2)! 通りあります。

まとめると, dp[n] は,
・dp[i]*(n-i-1)!
・dp[n-i-1]*i!
・(i-1)!*(n-i-2)!*(k-j)(k, j はそれぞれ右側の最小要素の座標, 左側の最小要素の座標)
の和に ${}_{n-1}C_{i-1}$ をかけたもの, になります。

まとめ

正直こんなの dp に決まってるんだから考える起点は「どんな dp にしようか」ってことだよね
- あとは cartesian tree の特徴を考えてホイ
  - 今回の場合, cartesian tree は数列の長さのみに依存する, という考察が重要だった(要素が 1, 2, 3, ... だろうと 1, 5, 6, 9, ... のように不規則だろうと, 最小の要素がどこにあるか, ということのみに注目すれば良い)
再帰的な特徴を見つけられれば後はそれを使って dfs するだけ, みたいなところある

const int MAXN = 101;
ll C[MAXN][MAXN];
ll fact[MAXN];
ll dp[MAXN];

ll dfs(int n, int MOD) {
    ll& ret = dp[n];
    if (ret >= 0) return ret;
    ret = 0;
    if (n <= 2) return ret;
    for (int i = 0; i < n; i++) {
        ll plus = 0;
        for (int j = 0; j < i; j++) for (int k = i+1; k < n; k++) {
            ll score = k-j;
            if (i > 0) (score *= fact[i-1]) %= MOD;
            if (n-i-2 >= 0) (score *= fact[n-i-2]) %= MOD;
            plus += score;
        }
        plus %= MOD;
        plus += fact[i]*dfs(n-i-1, MOD)%MOD;
        plus += fact[n-i-1]*dfs(i, MOD)%MOD;
        plus %= MOD;
        (plus *= C[n-1][i]) %= MOD;
        ret += plus;
    }
    ret %= MOD;
    return ret;
}

class BearPermutations2 {
public:
    int getSum(int N, int MOD) {
        for (int i = 0; i < MAXN; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i-1][j] + C[i-1][j-1];
                C[i][j] %= MOD;
            }
        }
        fact[0] = 1;
        for (int i = 1; i < MAXN; i++) fact[i] = (fact[i-1]*i)%MOD;
        memset(dp, -1, sizeof(dp));
        return dfs(N, MOD);
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 673 div2 hard:BearPermutations2

問題

解法

まとめ