AOJ 2439 Hakone - mayoko’s diary

問題

解法

まず, '-' があるところは順位が一意的に決まるので, 無視して良いです。与えられる文字列は 'U' と 'D' しか含まれないものとしましょう。

そしたら dp します。問題では今の中継地点での i 位の人が, 前の中継地点では何位なのかの場合の数を求めれば良いわけですが, 雰囲気としては以下のような戦略を取ります。

C[i] = 'D' なら, [0, i) に所望のチーム(順位が落ちてきたチーム)がないとおかしいので, ここで C[i] に対応するチームを確定させる
C[i] = 'U' なら, まだ所望のチームはどこかよくわからないので, 放っておく

具体的には以下のようにやります。

dp[i][j][k] = (i 番目まで見て, j チームはまだどこに割り当てられるか確定しておらず, k チーム割当先が残っているような場合の数) とします。割当先が残っている k チームというのは, C[l] = 'U' だったようなもので, まだどうしようか決めてないやつですね。

dp[0][0][0] = 1 であり, dp[n][0][0] が求めるべき値です。

このとき, dp[i][j][k] からは以下のように遷移します。

C[i] == 'D' の時,
- 割当先が決まっていない j チームの中から C[i] に割り当てるものを決めるが, i 番目のチームはどこに割り当てるか決めない。
  - 割り当て方は, j 通りあるので, dp[i+1][j][k] += dp[i][j][k] * j
- 割当先が決まっていない j チームの中から C[i] に割り当てるものを決め, かつ i 番目のチームを k チームのどれかにする。
  - 割り当て方は j * k 通りなので, dp[i+1][j-1][k-1] += dp[i][j][k] * j * k
C[i] == 'U' の時,
- その i 番目はどこにも割り当てない場合これは dp[i+1][j+1][k+1] += dp[i][j][k]
- i 番目を今までに割り当てられていない k 個のどれかに割り当てる場合, dp[i+1][j][k] += dp[i][j][k] * k

これで解けます。

ただ上の遷移をよく見ると j = k のところ以外は dp[i][j][k] = 0 となることに気付くので, O(N^2) で解けます。

O(N^2)

const int MAXN = 222;
const int MOD = 1e9+7;
ll dp[MAXN][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    string s;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        if (c != '-') s += c;
    }
    N = s.size();
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            if (s[i] == 'D') {
                dp[i+1][j] += dp[i][j] * j % MOD;
                if (j) dp[i+1][j-1] += dp[i][j] * j * j % MOD;
            } else {
                dp[i+1][j+1] += dp[i][j];
                dp[i+1][j] += dp[i][j] * j;
            }
        }
        for (int j = 0; j <= i+1; j++)
            dp[i+1][j] %= MOD;
    }
    cout << dp[N][0] << endl;
    return 0;
}

O(N^3)

const int MOD = 1e9+7;
ll dp[222][222][222];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
        int N;
    cin >> N;
    string s;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        if (c != '-') s += c;
    }
    N = s.size();
    dp[0][0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) for (int k = 0; k <= i; k++) {
            if (s[i] == 'D') {
                dp[i+1][j][k] += dp[i][j][k] * j % MOD;
                if (j > 0 && k > 0) dp[i+1][j-1][k-1] += dp[i][j][k] * j * k % MOD;
            } else {
                dp[i+1][j+1][k+1] += dp[i][j][k];
                dp[i+1][j][k] += dp[i][j][k] * k % MOD;
            }
        }
        for (int j = 0; j <= i+1; j++) for (int k = 0; k <= i+1; k++) {
            dp[i+1][j][k] %= MOD;
        }
    }
    cout << dp[N][0][0] << endl;
    return 0;
}