kmjp's blog

競技プログラミング参加記です

Codeforces #475 C. Cutting Rectangle

この回はほんとグダグダでした。
http://codeforces.com/contest/963/problem/C

問題

あるサイズA*Bの長方形のボードがある。
それぞれ辺に平行な切れ目を横p本縦q本入れ、全体を(p+1)*(q+1)個の長方形に分割したとする。

この時、それぞれのサイズとその個数が与えられる。(なお、長方形が回転されることはない)
元のA,Bの組み合わせは何通りか。

解法

分割後の長方形のサイズをW[i]*H[i]とする。
Wの集合をWall、Hの集合をHallとすると、w∈Wall、h∈Hallについてw*hの長方形が必ず存在しなければならないのでまずはそれを確認する。
あとはそれぞれのサイズの長方形を縦横何個ずつ並べるかのバリエーションを求めればよいので、各個数の最大公約数を求め、その約数を数え上げよう。

int N;
ll H[202020],W[202020],C[202020];
map<pair<ll,ll>,ll> M;
map<ll,vector<ll>> Ws;
map<ll,vector<ll>> Hs;
vector<ll> Wall,Hall;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll g=0;
	FOR(i,N) {
		cin>>W[i]>>H[i]>>C[i];
		M[{H[i],W[i]}]=C[i];
		g=__gcd(g,C[i]);
		Wall.push_back(W[i]);
		Hall.push_back(H[i]);
		Hs[H[i]].push_back(W[i]);
		Ws[W[i]].push_back(H[i]);
	}
	sort(ALL(Wall));
	sort(ALL(Hall));
	Wall.erase(unique(ALL(Wall)),Wall.end());
	Hall.erase(unique(ALL(Hall)),Hall.end());
	
	FORR(w,Ws) {
		if(w.second.size()!=Hall.size()) return _P("0\n");
		sort(ALL(w.second));
	}
	FORR(h,Hs) {
		if(h.second.size()!=Wall.size()) return _P("0\n");
		sort(ALL(h.second));
	}
	FOR(i,Hall.size()) {
		FOR(j,Wall.size()) {
			double a=M[{Hall[0],Wall[0]}];
			double b=M[{Hall[0],Wall[j]}];
			double c=M[{Hall[i],Wall[0]}];
			double d=M[{Hall[i],Wall[j]}];
			if(abs(b/a-d/c)>=1e-10) return _P("0\n");
		}
	}
	
	ll ret=0;
	for(ll a=1;a*a<=g;a++) {
		if(g%a==0) {
			ret++;
			if(a*a!=g) ret++;
		}
	}
	cout<<ret<<endl;
	
}

まとめ

問題を理解すれば難易度自体は低かった。