Codeforces #506: Div3. F. Multicolored Markers

途中の問題でTLEして全完逃してた。
https://codeforces.com/contest/1029/problem/F

問題

正整数A,Bが与えられる。
グリッド上で以下を満たす形状のうち、最短の外周を求めよ。

• A個の赤マスと、B個の青マスからなる。
• 上記(A+B)マスは、矩形領域を成す。
• 赤マスまたは青マス群の少なくとも片方は、矩形領域を成す。

解法

面積C=A+Bに対し、幅W・高さHを総当たりしよう。
もしそのような矩形を構築できれば、2*(H+W)が外周となりうる。

条件を満たすには、H*Wのグリッド内にAまたBの面積の矩形を配置できればよい。
Aの約数のうち、W以下の最大値をaとしたとき、A/a≦Hなら条件を満たす。

ll A,B,C,P;
vector<ll> D[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	P=1LL<<60;
	cin>>A>>B;
	C=A+B;
	
	for(ll a=1;a*a<=A;a++) if(A%a==0) D[0].push_back(a);
	for(ll a=1;a*a<=B;a++) if(B%a==0) D[1].push_back(a);
	
	x=y=-1;
	for(ll H=1;H*H<=C;H++) if(C%H==0) {
		ll W=C/H;
		
		while(x+1<D[0].size() && H>=D[0][x+1]) x++;
		while(y+1<D[1].size() && H>=D[1][y+1]) y++;
		
		if(x>=0 && A/D[0][x]<=W) P=min(P,2*(H+W));
		if(y>=0 && B/D[1][y]<=W) P=min(P,2*(H+W));
	}
	cout<<P<<endl;
}

まとめ

まだまだ簡単。