kmjp's blog

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

TopCoder SRM 705 Div2 Hard ChristmasBinaryTree

なんだこれ。
https://community.topcoder.com/stat?c=problem_statement&pm=14463

問題

深さDの完全二分木がある。
各頂点にN色のいずれかの色を塗ることを考える。
まず根にいずれかの色を塗ろう。

今頂点に色cが塗られている場合、左の子頂点はleft[c]、右の子頂点はright[c]で塗られる。
この木のスコアは、葉頂点のうち色がiの頂点がC(i)個あるとするとsum(C(i)^2) mod (10^9+7)である。
根頂点の色を任意に決められる場合、スコアの最大値を求めよ。

解法

木の左右は無視して、深さが1つ深くなると色cの頂点1個から色left[c]およびright[c]の頂点が1個ずつ増えると考える。
この関係を行列で表現すれば、行列のD乗に持ち込める。
あとは行列の累乗テクで高速に行列のD乗を求め、各根頂点の色に対応したスコアを総当たりしよう。
O(N^3*log(D))なので十分間に合う。

const int MAT=105;
ll G[MAT][MAT],G2[MAT][MAT];
ll mo=1000000007;
void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	int i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=(x==y);
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) h[x][y]=0;
			FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo;
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo;
		}
		FOR(x,n) FOR(y,n) h[x][y]=0;
		FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo;
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo;
		p>>=1;
	}
}

class ChristmasBinaryTree {
	public:
	int count(long long depth, vector <int> left, vector <int> right) {
		int N=left.size();
		ZERO(G);
		int i,j;
		FOR(i,N) G[left[i]][i]++, G[right[i]][i]++;
		powmat(depth-1,N,G,G2);
		
		ll ma=0;
		FOR(i,N) {
			ll tot=0;
			FOR(j,N) tot+=G2[j][i]*G2[j][i]%mo;
			ma=max(ma,tot%mo);
		}
		return ma;
		
		
	}
}

まとめ

これ900ptだったかな。