AOJ 2439 - 箱根駅伝 (Hakone)

めちゃくちゃ教育的🧐

問題

箱根駅伝のある中継所における「各チームの通過順位」と「前の中継所からの順位変動」が与えられる
具体的には、c[i]がこの中継所をi番目に通過したチームの前の中継所からの順位変動を表し、
c[i] = '-'のとき) 順位は変わらない
c[i] = 'U'のとき) 順位が上がった
c[i] = 'D'のとき) 順位が下がった
ことを表す
前の中継所の各チームの通過順として考えられるものが何通りあるか求めよ

1 <= n <= 200

解法

まずc[i]='-'のチームはもう前の中継所の順位が決まっちゃってるから考慮しなくていい
これらは消し、cが'U'か'D'のチームだけ残った状態にする

例えばサンプル2(UUDD)について考える
求めたいのは↓の画像のような状態から始め、左側の各頂点と右側の各頂点を結んでn個のペアを作るような結び方の個数である
(ただし右側の各頂点からちょろっと伸びてる線の向きは守らないといけない)
f:id:creep040:20180927061046p:plain
例えば↓のような結び方がある
f:id:creep040:20180927061101p:plain
これをdpで数え上げていく
dp[i][j][k]: 上からi番目まで見て、左側の頂点はj個、右側の頂点はk個まだペアが決まっていない状態の個数
とするとdp[0][0][0]は1で、答えはdp[n][0][0]になる
以下左側の頂点を上から順にl[0], l[1], ..., l[n]とし、右側の頂点をr[0], ...とする
遷移は

(c[i]=='D'のとき)
r[i]は絶対にj個のうちどれか1個とペアにしないといけない(j通り)
l[i]はk個のうちどれか1個とペアにしてもいい(k通り)し保留してもいい
ペアにする場合 -> dp[i+1][j-1][k-1] += dp[i][j][k] * j * k
ペアにしない場合 -> dp[i+1][j][k] += dp[i][j][k] * j

(c[i]=='U'のとき)
r[i]のペアは今すぐには確定できないから保留するしかない
l[i]はk個のうちどれか1個とペアにしてもいい(k通り)し保留してもいい
ペアにする場合 -> dp[i+1][j][k] += dp[i][j][k] * k
ペアにしない場合 -> dp[i+1][j+1][k+1] += dp[i][j][k]

これでO(n^3)で解ける
けどよく見ると遷移は全て「jもkも1減る」or「jもkも変わらない」or「jもkも1増える」のどれかだから常にj==kになることがわかる
(グラフで考えれば当たり前のこと)
だから
dp[i][j]: 上からi番目まで見て、左側も右側もまだペアが決まってない頂点がj個ある状態の数
としてよくて、O(n^2)で解ける

#define int long long

int n, dp[202][202];
char c[202];

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> c[i];
		if (c[i]=='-') i--, n--;
	}
	dp[0][0] = 1;
	rep(i,n) rep(j,n) {
		// r[i]のペアは絶対確定する l[i]のペアは確定させるかさせないか選べる
		if (c[i]=='D') {
			if (j) (dp[i+1][j-1] += dp[i][j]*j %mod *j) %= mod;
			(dp[i+1][j] += dp[i][j]*j) %= mod;
		}
		// r[i]のペアは絶対確定しない l[i]のペアは選べる
		else {
			(dp[i+1][j] += dp[i][j]*j) %= mod;
			(dp[i+1][j+1] += dp[i][j]) %= mod;
		}
	}
	cout << dp[n][0] << endl;
}