Codeforces #917 : Div2 F. Construct Tree

割と力技。
https://codeforces.com/contest/1917/problem/F

問題

(N+1)頂点の木を成す無向グラフを作りたい。
今N個の辺の長さL[i]が与えられる。
直径がDの木を作れるか判定せよ。

解法

Lのうち大きな2つを合わせてDを超える場合、解はなし。
そうでない場合、bitsetで、以下を管理しよう。
dp(x,y) := ある点から、伸びる最大のパス長がxで、2番目のパス長がyである状態があるかどうか。

最大の長さの辺を使わない場合どんな長さの直径を作れるか判定しよう。

Lの最大値をMとする。

• dp(0,D-M)がTrueの場合、そこにMの辺を加えて直径Dのグラフを作れる。
• dp(i,D-i)かつiもD-iもM以下の場合、その点に長さMの辺を追加しても直径Dを維持できる。

int T,N,D,L[2020];

bitset<2020> B[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>D;
		FOR(i,N) cin>>L[i];
		sort(L,L+N);
		if(L[N-1]+L[N-2]>D) {
			cout<<"No"<<endl;
			continue;
		}
		FOR(i,D+1) B[i].reset();
		B[0][0]=1;
		FOR(i,N-1) {
			for(j=D;j>=0;j--) {
				if(j+L[i]<=D) B[j+L[i]]|=B[j];
				B[j]|=B[j]<<L[i];
			}
		}
		int ok=B[0][D-L[N-1]];
		for(i=0;i<=D;i++) if(i>=L[N-1]&&D-i>=L[N-1]&&B[i][D-i]) ok=1;
		if(ok) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
}

まとめ

コードは割と短め。