Codeforces #866 : Div1 B. The Butcher

いまいちだった回。
https://codeforces.com/contest/1819/problem/B

問題

グリッド状の四角形がある。
これを辺に平行な線で2つに分け、片方は箱に入れ、もう片方は再度2つに分ける、という作業を繰り返す。
計N-1回この処理を行い、計N個の四角形に分割できたとする。
途中四角形の回転ができないとする。

N個の四角形のサイズが与えられるとき、あり得る最初の四角形のサイズを列挙せよ。

解法

初手を縦または横に分割することを考えると、初期状態の縦及び横のサイズは、N個の四角形の縦及び横の最大値と一致する。
よって、あり得る最初の四角形のサイズは2通りである。
あとは縦に分割できる限り分割し、その後横に分割できる限り分割・・・・という作業を繰り返し、入力のN個の四角形を作れるか試せばよい。

int T,N,A[202020],B[202020];

multiset<pair<ll,ll>> X,Y;
vector<pair<ll,ll>> ret;

int dfs(multiset<pair<ll,ll>>& A,multiset<pair<ll,ll>>& B,pair<ll,ll> p) {
	if(p.first<0||p.second<0) return 0;
	if(A.empty()) {
		return 1;
	}
	auto it=A.lower_bound({p.first,0});
	int x=0;
	if(it!=A.end()&&it->first==p.first) {
		auto q=*it;
		A.erase(it);
		B.erase(B.find({q.second,q.first}));
		x=dfs(A,B,{p.first,p.second-q.second});
		A.insert(q);
		B.insert({q.second,q.first});
	}
	it=B.lower_bound({p.second,0});
	if(x==0&&it!=B.end()&&it->first==p.second) {
		auto q=*it;
		B.erase(it);
		A.erase(A.find({q.second,q.first}));
		x|=dfs(A,B,{p.first-q.second,p.second});
		B.insert(q);
		A.insert({q.second,q.first});
	}
	return x;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		X.clear();
		Y.clear();
		int maX=0,maY=0;
		ll sum=0;
		FOR(i,N) {
			cin>>A[i]>>B[i];
			X.insert({A[i],B[i]});
			Y.insert({B[i],A[i]});
			maX=max(maX,B[i]);
			maY=max(maY,A[i]);
			sum+=1LL*A[i]*B[i];
			
		}
		
		ret.clear();
		if(sum%maX==0&&dfs(X,Y,{sum/maX,maX})) ret.push_back({sum/maX,maX});
		if(sum%maY==0&&dfs(X,Y,{maY,sum/maY})) ret.push_back({maY,sum/maY});
		sort(ALL(ret));
		ret.erase(unique(ALL(ret)),ret.end());
		cout<<ret.size()<<endl;
		FORR2(a,b,ret) cout<<a<<" "<<b<<endl;
		
	}
}

まとめ

結果だけ見ると簡単なんだけど、本番結構手間取ってるな。