Codeforces #999 : D. Kevin and Numbers

最初の1時間しかAC出せなかった…。
https://codeforces.com/contest/2061/problem/D

問題

整数の多重集合A,Bが与えられる。

Aのうち、差の絶対値が1以下の2要素を選び、その和に置き換える、ということを繰り返し、AをBに一致できるか判定せよ。

解法

和に置き換える際はペアにする要素の候補がいくつかあるが、逆に巻き戻すことを考えるとばらし方は一通りになる。
よって、逆にBからAに巻き戻せるか判定しよう。
まずsum(A)=sum(B)であることを確認したうえで、以下をA,Bが空になるまで行えばよい。

• Bの最大値よりAの最大値が大きい場合、一致不可
• Bの最大値とAの最大値が一致する場合、両者を取り除く
• Bの最大値よりAの最大値が小さい場合、Bの最大値を2要素に分割して置き換える。

int T,N,M;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		ll sum=0;
		cin>>N>>M;
		multiset<ll> A,B;
		FOR(i,N) {
			cin>>x;
			sum+=x;
			A.insert(x);
		}
		FOR(i,M) {
			cin>>x;
			sum-=x;
			B.insert(x);
		}
		if(sum) {
			cout<<"NO"<<endl;
			continue;
		}
		while(B.size()) {
			if(*B.rbegin()==*A.rbegin()) {
				x=*B.rbegin();
				B.erase(B.find(x));
				A.erase(A.find(x));
			}
			else if(*B.rbegin()<*A.rbegin()) {
				break;
			}
			else {
				x=*B.rbegin();
				B.erase(B.find(x));
				B.insert(x/2);
				B.insert(x-x/2);
			}
		}
		if(B.size()) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
}

まとめ

これはすぐ思いついたな。