PKU 2362 Square

夏に苦労したPKU1011 Sticksを彷彿とさせる探索問題。今回は2回目でACしたけど。

問題概要

それぞれの長さの与えられたn本の棒（n≦20）を使って正方形を作ることができるか判定せよ。

この問題、使わない棒があってもいいともダメとも書いてないしサンプルからじゃ読み取れないような気がするのだけど……
僕は英語力が非常にアレなので英語読める方いたら指摘お願いします。
(http://acm.pku.edu.cn/JudgeOnline/problem?id=2362)

試行錯誤

使わない棒があっていいと思っていたので最初にそんな感じのコードを書いてとりあえず送ってみる。→TLE

1 2 4 8 16 ... 8192みたいなインプットあったら（組み合わせが爆発して）爆死するに決まってるじゃないか。
でもWA出てないから問題がどっちなのかよくわからない……ので入出力セットを探してきた。(http://plg1.cs.uwaterloo.ca/~acm00/)
どうも全ての棒を使わないといけないらしい。そんな感じのコードを書く。

ローカルで実行→うーん反応が返ってこない、ちょっと枝刈り考えてみよう。

解法

深さ優先探索+枝刈り

最初に長さでソート。辺の順序は関係ないので、1番目の辺を作るのにつかった最初の棒の長さ≧2番目の辺の最初の（ｒｙ≧3番目の（ｒｙという枝刈りを入れる。これで大体探索量1/24.
使ってない長さの棒を全てつかっても辺の長さに届かないような状態を探索している場合も枝刈りした。これでどのくらい計算量が減ったかわからないけれど手元ではジャッジデータが一瞬で終わるようになった。

送信すると2100MSくらいでAC.にしてもSubmissionみるとほとんど100MS以内とかで終わってるぞ……0MSの人もたくさんいるし。
実は凄いスマートな解法があるんじゃないのかこれ。

int n,l[20],prevbegin;
bool use[20];

bool dfs(int cur,int r,int clen,int mlen)
{
	if(r==0)return 1;
	
	for(int i=cur;i<n;i++)
	if(!use[i]&&clen+l[i]<=mlen)
	{
		
		int ncur=cur+1,nr=r,nlen=clen+l[i];
		if(nlen==mlen)nlen=0,nr--,ncur=0;

		//上に書いた残りを全て使っても足りない場合のbrunch cut
		int s=0;
		for(int j=i;j<n;j++)if(!use[j])s+=l[j];
		if(s+clen<mlen)continue;

		//辺で最初に使う棒の長さを降順にする
		int tmp=prevbegin;
		if(cur==0)
		{
			if(prevbegin>i)continue;
			prevbegin=i;
		}
		
		use[i]=1;
		if(dfs(ncur,nr,nlen,mlen))return 1;
		use[i]=0;
		
		if(cur==0)prevbegin=tmp;
	}
	return 0;
}

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		cin>>n;
		rep(i,n)cin>>l[i];
		
		sort(l,l+n,greater<int>());
		int s=accumulate(l,l+n,0),len=s/4;
		if(len*4!=s)
		{
			cout<<"no"<<endl; continue;
		}
		fill(use,use+n,0);
		prevbegin=0;
		
		if(dfs(0,4,0,len))cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
	return 0;
}