こういう難易度の変え方はいいね。
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の日本語訳って何?デカルト木で検索してもほとんどヒットしないのだけど。