kmjp's blog

競技プログラミング参加記です

TopCoder SRM 673 Div2 Hard BearPermutations2

こういう難易度の変え方はいいね。
https://community.topcoder.com/stat?c=problem_statement&pm=14084

問題

数列に対するCartesian treeの構築及びスコアの計算方法はDiv1 mediumと同一。
TopCoder SRM 673 Div1 Medium BearPermutations - kmjp's blog

ただし、こちらは1~NからなるPermutation N!通りについて、そのスコアの総和を求めよ。

解法

N要素の数列のスコアは最大100より大きくなるため、Div1 MediumのSを100以上まで試すのは不可。

dp(N,C) := (N要素のCartesian Treeのうち、根が左端からC個目にあるようなもののスコアの総和)としてDPしていく。

  • C=1またはC=Nの時、根は1個しか子頂点を持たないのでdp(N,C) = sum_i(N-1,i)となる。
  • 1<C<Nの時、根は2個の子頂点を持つ。根の左側のSubtreeの頂点数をL=C-1、右側の頂点数をR=N-Cとする。
    • 左側のSubtreeによるdp(N,C)への影響を考える。
    • まず、N要素のうち根を除く(N-1)要素において、どのL個が左のSubtreeに行くか…と考えると全体でComb(N-1,L)通りある。これは最後にdp(N,C)に掛けよう。以後、両SubTreeは1~L,1~Rの連番のみで構成されていると考える。
    • 左側のSubtreeの根が、L要素中LC番目にあるとし、LCを1~Lまで総当たりしよう。
      • まず根がLC番目に来るので、その事によりdp(N,C)に(C-LC)分のスコアを寄与する。そのような木の構築法は、左のSubtreeにおいて根以外の頂点の並べかた(L-1)!通りと、右側のSubTreeの頂点の並べかたR!通り、合わせて(C-LC)*(L-1)!*R!通りある。
    • そのようなSubtreeのスコアは当然dp(L,LC)である。左側がdp(L,LC)の対象となるような木となる並べ方について、右側のSubTreeの並べ方分R!だけ同じ並べ方を取れるので、dp(L,LC)*R!だけdp(N,C)に寄与する。
    • 右側も左側同様、根の位置RCを1≦RC≦Rの範囲で総当たりし、RC*(R-1)!*L!とdp(R,RC)*L!を足しこんでいけば良い。
ll memo[105][105];
ll fact[201];
const int CN=401;
ll C[CN][CN];


class BearPermutations2 {
	public:
	ll mo;
	
	ll dpdp(int N,int L) {
		
		if(N<=1) return 0;
		if(memo[N][L]>=0) return memo[N][L];
		
		int i;
		ll ret=0;
		
		if(L==0 || L==N-1) {
			FOR(i,N-1) ret+=dpdp(N-1,i);
		}
		else {
			int i;
			int R=N-L-1;
			FOR(i,L) {
				ret += (i+1)*fact[L-1] % mo * fact[R] % mo;
				ret += dpdp(L,i) * fact[R] % mo;
			}
			FOR(i,R) {
				ret += (i+1)*fact[R-1] % mo * fact[L] % mo;
				ret += dpdp(R,i) * fact[L] % mo;
			}
			ret = ret % mo * C[N-1][L];
		}
		
		
		return memo[N][L]=ret%mo;
	}
	
	int getSum(int N, int MOD) {
		mo = MOD;
		
		int i,j;
		fact[0]=1;
		FOR(i,100) fact[i+1]=fact[i]*(i+1)%mo;
		FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
		
		MINUS(memo);
		ll ret=0;
		FOR(i,N) ret += dpdp(N,i);
		return ret%mo;
	}
}

まとめ

Cartesian Treeの日本語訳って何?デカルト木で検索してもほとんどヒットしないのだけど。