Codeforces #631 Div1 C. Drazil Likes Heap

また変な設定の問題。
http://codeforces.com/contest/1329/problem/C

問題

高さHのヒープが与えられる。このヒープでは上位のノードほど大きい値を持っており、最大値を容易に取得可能である。
ここで、ヒープ中で任意のindexを指定し、その要素を削除する（その際その下位のノードは、ヒープの特性を生かすように上に移動する）とする。

このヒープを高さGとしたい。
その時、残された値の総和を最小化し、各手順でのノード探索の再帰回数を列挙せよ。

解法

できるだけ上位のノードを削除すれば、大きな値が削除されるので良い。
そこで、ノードを上位からDFSし、「ここでノード削除を繰り返すと高さがG未満になってしまう」ということが起こる直前まで削除していこう。

int T;
int G,H;
int A[1<<21];
int hei[2<<20];

vector<int> R;

int trydfs(int cur) {
	if(A[2*cur]==0 && A[2*cur+1]==0) {
		return cur;
	}
	if(A[2*cur]>A[2*cur+1]) return trydfs(2*cur);
	return trydfs(2*cur+1);
}

int godfs(int cur) {
	int ret=A[cur];
	if(A[2*cur]==0 && A[2*cur+1]==0) {
		A[cur]=0;
	}
	else {
		if(A[2*cur]>A[2*cur+1]) {
			A[cur]=godfs(2*cur);
		}
		else {
			A[cur]=godfs(2*cur+1);
		}
	}
	return ret;
}



void dfs(int cur) {
	while(A[cur]) {
		int tr=trydfs(cur);
		if(hei[tr]<=G) break;
		R.push_back(cur);
		godfs(cur);
	}
	if(A[cur]==0) return;
	dfs(cur*2);
	dfs(cur*2+1);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	FOR(i,20) {
		FOR(j,1<<i) hei[(1<<i)+j]=i+1;
	}
	
	cin>>T;
	while(T--) {
		cin>>H>>G;
		R.clear();
		FOR(i,(1<<H)-1) {
			cin>>A[i+1];
		}
		dfs(1);
		
		ll sum=0;
		for(i=1;i<(1<<G);i++) sum+=A[i];
		cout<<sum<<endl;
		FORR(v,R) cout<<v<<" ";
		cout<<endl;
		FOR(i,(1<<H)-1) A[i+1]=0;
	}
}

まとめ

問題を解くより問題を理解するのに手間取りそう。