TopCoder SRM 783 : Div1 Easy Div2 Hard CardboardBoxes

問題文が読みにくいなぁ…。
https://community.topcoder.com/stat?c=problem_statement&pm=16060&rd=17903

問題

幅≦奥行な直方体の箱を考える。
この箱は12個の板を張り合わせた段ボールのような形状をしている。
板の総表面積がSの時、3辺の形状としてあり得るのは何通りか。

解法

奥行をL、幅をW、高さをHとする。

• 側面の4個の板の面積の和は2H(L+W)
• 天板は2*(W/2)*(L+W)、底面も同じ

結局これらの和は2*(W+L)*(W+H)であり、W≦LのうちこれがSとなる組み合わせを探る問題となる。
Sが偶数なのは必須として、あとは(W+L)*(W+H)=S/2となるよう、S/2の約数を総当たりしよう。

ここで、A*B=S/2となる約数があったとすし、W+L=A、W+H=BとなるW,L,Hを考えよう。

• W≦LよりWはA/2以下
• Hが最低1はないといけないのでWはH-1以下

とするとWはmin(A/2,H-1)通り取れることがわかる。

class CardboardBoxes {
	public:
	ll hoge(ll x,ll y) {
		return min(x/2,y-1);
	}
	
	long long count(long long S) {
		if(S%2) return 0;
		S/=2;
		ll ret=0;
		for(ll a=1;a*a<=S;a++) if(S%a==0) {
			ret+=hoge(a,S/a);
			if(a!=S/a) ret+=hoge(S/a,a);
		}
		
		return ret;
		
	}
}

まとめ

これ箱の形状を理解するまでが一番大変な気がする…。