AtCoder ABC #226 : G - The baggage

8問制のABCになってから、初めて時間内に全完した気がする。
https://atcoder.jp/contests/abc226/tasks/abc226_g

問題

重さ1,2,3,4,5の荷物がそれぞれA[i]個ある。
また、重さ1,2,3,4,5まで持てる人がB[i]人いる。
各人は、持てる重さの上限を超えない範囲で、複数の荷物を持つことができる。

この人ら全員で、全荷物を持つことができるか。

解法

Editorialと違うけど、自分は枝刈りDFSで解いた。
重さxの荷物を、重さyを持てる人がmin(A[x],B[y])持つことにする、というのをDFSしていった。
ただ、これだとメモ化再帰してもTLEしてしまった。

以下のコードでは、若干以下の手順で枝刈りしている。

• 荷物の重さの総和より、人の持てる重さの方が多いなら、重さ1の人・荷物は無視してよい。
  • 重さ2以上の荷物を、すべて人に割り当てることができたら、残りの荷物を人に割り当てる手段がある。
• 重さ2の荷物と重さ2を持てる人がいたら、積極的にそこを割り当てる。あえて先に重さ2を持てる人に重さ1の荷物を割り当てて得することはない。
• 重さ4の荷物と重さ4を持てる人がいたら、積極的にそこを割り当てる。そうでない場合、重さ5を持てる人が重さ4の荷物を持つことになるが、これで得することはない。
• 重さ5の荷物と重さ5を持てる人がいたら、積極的にそこを割り当てる。重さ5の荷物は、重さ5を持てる人しか持てない。

int T;
ll A[6],B[6];
int ok;
set<vector<ll>> S;

void dfs(vector<ll> V) {
	ll a=min(V[0],V[3]);
	V[0]-=a;
	V[3]-=a;
	a=min(V[2],V[5]);
	V[2]-=a;
	V[5]-=a;
	if(S.count(V)) return;
	S.insert(V);
	int i;
	a=0;
	FOR(i,3) a+=V[i];
	if(a==0) {
		ok=1;
		return;
	}
	int x,y;
	for(x=2;x<=4;x++) if(V[x-2]) {
		for(y=x;y<=5;y++) if(V[y+1]) {
			ll m=min(V[x-2],V[y+1]);
			vector<ll> W=V;
			W[x-2]-=m;
			W[y+1]-=m;
			if(y-x>=2) W[y-x+1]+=m;
			dfs(W);
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		ll sum=0;
		FOR(i,5) {
			cin>>A[i+1];
			sum+=A[i+1]*(i+1);
		}
		FOR(i,5) {
			cin>>B[i+1];
			sum-=B[i+1]*(i+1);
		}
		if(sum>0) {
			cout<<"No"<<endl;
			continue;
		}
		ok=0;
		S.clear();
		vector<ll> V;
		ll a=min(A[5],B[5]);
		A[5]-=a;
		B[5]-=a;
		if(A[5]) {
			cout<<"No"<<endl;
			continue;
		}
		for(i=2;i<=4;i++) V.push_back(A[i]);
		for(i=2;i<=5;i++) V.push_back(B[i]);
		dfs(V);
		if(ok) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

まとめ

Hより手間取った。