読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Codeforces #245 Div1 C. Guess the Tree

Codeforces

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

問題

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

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

解法

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

  • 子が1個ということはありえないので、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が2個以上あり、かつ合計(C[i]-1)分のサブツリーを割り当て切れればよい。2個未満なら木の生成が不可。
  • 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");
}

まとめ

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

広告を非表示にする