kmjp's blog

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

Codeforces #332 Div2 D. Spongebob and Squares

ひどい手抜きだ…。
http://codeforces.com/contest/599/problem/C

問題

あるH*Wのグリッドがあるとする。
このグリッドのスコアは、内部のセルを一部選択してできる正方形の数の和だとする。

スコアXが与えられる。
そのようなスコアを成すグリッドサイズH*Wを求めよ。

解法

W≧Hの場合を考える。
このグリッドからは、大きさk*kの正方形は(H-k)*(W-k)個とれる。
よってH*WのグリッドのスコアF(H,W)は F(H,W) = \sum_{k=0}^{H-1} \( (H-k)*(W-k) \) = \frac{H(H+1)}{2}W  - \frac{H(H-1)(H+1)}{6}である。
あとはHを1~200000程度まで総当たりし、W≧Hである整数Wを列挙すればよい。

ll X;
vector<pair<ll,ll> > V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X;
	for(ll H=1;H<1601010;H++) {
		ll a = H*(H+1)/2;
		ll b = -H*(H-1)*(H+1)/6;
		if(X-b<=0) continue;
		if((X-b)%a) continue;
		ll W = (X-b)/a;
		
		if(H<=W) V.push_back({H,W});
		if(H<W) V.push_back({W,H});
	}
	sort(ALL(V));
	cout<<V.size()<<endl;
	FORR(r,V) cout<<r.first<<" "<<r.second<<endl;
}

まとめ

本番もう少しごちゃごちゃした式を立ててしまったため、オーバーフロー回避で10^6までしかループしなかったらWAした。