Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 2439 - Hakone

問題文 : Hakone

概要 : (日本語なので略)


解法 :

この問題で数え上げなければいけないものは、
「前の区間の順位と今の区間の順位の間の順位の移り変わりとして正しいマッチングの個数」
である。(下図中の青線の引き方の総数)

f:id:kagamiz:20160504151138p:plain:h400

これは、[今どの順位までを見たか][自分より上の順位でまだ前回の順位とマッチングが決まっていない場所は何箇所か]
という DP をするとうまく求まる。答えは dp[$N$][0]である。
このとき、上図の「前回の順位」と「今回の順位」を同時に見ていかないといけないというのがこの DP を考える上での難しさである。

ここで, 順位表中の 3 つの値 -, U, D ごとの遷移を考えてみる。

  • -の時の遷移

-のときは、今回の $i$ 番目の順位は前回の $i$ 番目の順位と等しいので,
自分より上の順位でマッチングが決まっていないものの個数は減らない。
すなわち, dp[$i+1$][$j$] += dp[$i$][$j$] と遷移してやれば良い。

  • Uの時の遷移

U のときは, 遷移先の状態が 2 つ存在しうる。
どちらの遷移先でも、今回の $i$ 番目の順位のチームは前回$i+1$位以下だったことが分かっている。

前回の $i$ 番目の順位のチームが今回 $i+1$ 位以下である場合

このとき、[自分より上の順位でまだ前回の順位とマッチングが決まっていない場所]が一箇所増えるので、
dp[$i+1$][$j+1$] += dp[$i$][$j]$ と遷移する。

前回の $i$ 番目の順位のチームが今回 $i - 1$ 位以上である場合

このとき、前回の$i$位のチームはまだマッチングが決まっていない $j$ 個の場所のいずれかと結びつく。
しかし、今回の $i$ 位のチームがまだマッチングが決まっていないので、マッチングが決まっていないチームの変わらず、
dp[$i+1$][$j$] += $j \times$ dp[$i$][$j$] と遷移する。

  • Dの時の遷移

D のときも, U の時同様遷移先の状態が 2 つ存在しうる。
どちらの遷移先でも、今回の $i$ 番目の順位のチームは前回$i-1$位以上だったことが分かっている。

前回の $i$ 番目の順位のチームが今回 $i+1$ 位以下である場合

このとき、今回の$i$位のチームはまだマッチングが決まっていない $j$ 個の場所のいずれかと結びつく。*1
しかし、前回の $i$ 位のチームがまだマッチングが決まっていないので、マッチングが決まっていないチームの変わらず、
dp[$i+1$][$j$] += $j \times$ dp[$i$][$j$] と遷移する。

前回の $i$ 番目の順位のチームが今回 $i - 1$ 位以上である場合

このとき、今回の $i$ 番目のチームも前回の $i$ 番目のチームもマッチングを引く通り数として$j$ 通りの方法がある。
このとき、マッチングが決まっていない箇所が 1 減る事がわかる。よって、
dp[$i+1$][$j-1$] += $j^2 \times$ dp[$i$][$j$] と遷移する。


この遷移を元に DP をしてやれば良い。
時間計算量は $O(N^2)$ である。

コード :

#include <bits/stdc++.h>

using namespace std;

typedef long long Int;
const int MOD = 1000000007;

Int dp[201][201];

int main()
{
    int N;
    char s[256];

    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%s", &s[i]);

    dp[0][0] = 1;

    for (int i = 0; i < N; i++){
        for (int j = 0; j <= N; j++){
            if (s[i] == '-'){
                dp[i + 1][j] += dp[i][j];
                dp[i + 1][j] %= MOD;
            }
            if (s[i] == 'U'){
                dp[i + 1][j] += dp[i][j] * j;
                dp[i + 1][j] %= MOD;
                if (j < N){
                    dp[i + 1][j + 1] += dp[i][j];
                    dp[i + 1][j + 1] %= MOD;
                }
            }
            if (s[i] == 'D'){
                dp[i + 1][j] += dp[i][j] * j;
                dp[i + 1][j] %= MOD;
                if (j > 0){
                    dp[i + 1][j - 1] += dp[i][j] * j * j;
                    dp[i + 1][j - 1] %= MOD;
                }
            }
        }
    }

    printf("%lld\n", dp[N][0]);

    return (0);
}

補足 :
この DP は後に箱根 DP と呼ばれる様になったらしいです。
順列を2つ扱う問題だと確かに応用できそうですね。

類題 :
LittleElephantAndPermutationDiv1(SRM592Div1Medium)
この dp を知っているとすごく良く見通しが立ちます。

*1:「今回の順位と前回の順位でマッチングが決まっていない個数」を一つの状態として横着しているため考えづらいが、遷移を考えると、前回の順位でマッチングが決まっていない場所もちょうど $j$ 個になることが分かる。