Codeforces #245 Div1 C. Guess the Tree

ここから適当解法。
http://codeforces.com/contest/429/problem/C

問題

N要素の整数配列C[i]が与えられる。
以下の根付き木を作成できるか答えよ。

1. N頂点からなり、各頂点のサブツリーの頂点数はC[i]に一致する(C[i]と登場順は一致しなくてもよい)
2. 子を持つ頂点は、常に２個以上の子を持つ。

解法

条件より以下のことがわかる。

• 子が１個ということはありえないので、C[i]==2の時は作成不可。
• 根の頂点のサブツリーは木全体に相当するはずなので、C[i]の最大値はN。
• C[i]=1となる要素がNの半分以上を占める。

特に最後の条件より、C[i]>1、すなわち子を持つ頂点は11個以下になる。
よって、そのようなC[i]を昇順ソートし、各頂点がどの子になるかを総当たりする手がある。
この場合10!通りの総当たりなのでなんとか間に合う。

また、Editorialではそのような頂点の状態を3つで表現し、3^(N/2) に比例した回数のDPを行う手法を示している。

ただ、今回は以下の適当貪欲解法で通った。

• C[i]を降順ソートし、i=0～(N-1)で順に処理する。根となるC[0]は割り当て済みとする。
• C[i]の処理時、C[i]が未割当なら、条件を満たす木の生成が不可。
• j>iとなるC[j]のうち、合計がC[i]-1になるまで貪欲にC[i]の子となるよう割り当てる。
  • 各iに対し、C[i]>1なら割り当てるjが２個以上あり、かつ合計(C[i]-1)分のサブツリーを割り当て切れればよい。２個未満なら木の生成が不可。
• i=N-1まで処理が完了できたら木が生成可能。

上記アイデアは、「サブツリー頂点数C[i]の頂点がある場合、C[i+1]以降の未割当頂点のうち最大のものがC[i]に接続しなければならない」という見解に基づいている。
でもこれで本番通るとは思わなかった。

int N;
int C[30];
vector<int> V;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	x=0;
	FOR(i,N) {
		cin>>C[i];
		if(C[i]==2) return _P("NO\n");
		V.push_back(C[i]);
	}
	
	sort(V.begin(),V.end());
	int mask=1<<(N-1);
	if(V[N-1]!=N) return _P("NO\n");
	for(i=N-1;i>=0;i--) {
		if((mask & (1<<i))==0) return _P("NO\n");
		if(V[i]==1) continue;
		int x=V[i]-1,y=0;
		for(j=i-1;j>=0;j--) {
			if(x>=V[j] && (mask & (1<<j))==0)  {
				x-=V[j];
				y++;
				mask |= 1<<j;
			}
		}
		if(x!=0 || y<2) return _P("NO\n");
	}
	return _P("YES\n");
}

まとめ

他にも若干貪欲解法で通った人がいたようだ。