Educational DP Contest T問題：Permutation

問題. Permutation

各文字が '<' か '>' からなる長さ $n - 1$ の文字列 $s$ が与えられる． $N = \{1, 2, \ldots, n\}$ 上の順列 $\pi$ で次の条件を満たすものが何通りあるか求めよ．
　・ $s_i$ が '<' ならば $\pi_{i} < \pi_{i + 1}$
　・ $s_i$ が '>' ならば $\pi_{i} > \pi_{i + 1}$
制約： $2 \le n \le 3,000$

解法

解法が思いつかなかったので kmjpさんのブログを参考にしました．
　Educational DP Contest : T - Permutation - kmjp's blog

順列を先頭から決めていくことを考えます．初めから $i - 1$ 番目までの列 $\pi_1, \ldots, \pi_{i-1}$ が決まっており $i$ 番目の要素 $\pi_i$ を決めます．また， $X \subseteq N$ をまだ選ばれていない要素の集合とします．このとき， $s_{i-1}$ が '<' ならば $\pi_i$ は $X$ の中で $\pi_{i - 1}$ よりも大きいものしか選ぶことができません．もし， $\pi_{i - 1}$ が 5 で $X = \{1, 3, 6, 8\}$ のとき選べるのは $6, 8$ となります．また， $X' = \{1, 2, 7, 9\}$ のとき選べるのは $7, 9$ となります．ここで， $\pi_i$ 以降での順列の数は $X$ と $X'$ で等しくなります．この2つの共通点は $X$ と $X'$ の中で $\pi_{i-1}$ が何番目に小さいかが等しいということです．したがって，dp[i][j] を $1$ から $i$ 番目までを決めたときのまだ選ばれていない $N$ の要素の中で $i$ 番目の要素が $j$ 番目に小さい順列の数　として動的計画法を行います．遷移は，
　・ $s_{i-1} =$ '<' の場合：dp[i][j] = dp[i - 1][j - 1] + ... + dp[i - 1][1]
　・ $s_{i-1} =$ '>' の場合：dp[i][j] = dp[i - 1][j + 1] + ... + dp[i - 1][n - i + 2]
となります．ここで，各場合での右辺の和は累積和で $i$ を決める前に前処理を $O(n)$ 時間でを行い，各 $j$ に対して $O(1)$ 時間で部分和を求めることができます．よって全体の計算時間は $O(n^2)$ となります．

計算時間： $O(n^2)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    constexpr ll MOD = 1e9 + 7;

    int n;
    string s;
    cin >> n >> s;

    vector<vector<ll>> dp(2, vector<ll>(n + 1));
    auto &cur = dp[0], &nxt = dp[1];

    for (int i = 1; i <= n; ++i) cur[i] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= n - i + 2; ++j) {
            cur[j] += cur[j - 1];
            nxt[j] = 0;
        }

        for (int j = 1; j <= n - i + 1; ++j) {
            if (s[i - 2] == '<') (nxt[j] += (cur[j] - cur[0] + MOD)) %= MOD;
            else (nxt[j] += (cur[n - i + 2] - cur[j] + MOD)) %= MOD;
        }
        swap(cur, nxt);
    }

    cout << cur[1] << endl;

    return 0;
}

　
上のソースコードをまとめるとほんの少し高速になります．

修正したソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    constexpr ll MOD = 1e9 + 7;

    int n;
    string s;
    cin >> n >> s;

    vector<int> cur(n + 1, 1), nxt(n + 1);
    cur[0] = 0;

    for (int i = 2; i <= n; ++i) {
        if (s[i - 2] == '<') {
            for (int j = 1, sum = 0; j <= n - i + 1; ++j)
                nxt[j] = ((sum += cur[j]) %= MOD);
        }
        else {
            for (int j = n - i + 1, sum = 0; 1 <= j; --j)
                nxt[j] = ((sum += cur[j + 1]) %= MOD);
        }
        swap(cur, nxt);
    }

    cout << cur[1] << endl;

    return 0;
}