TopCoder SRM 655 Div2 Medium FoldingPaper2

ちょっと頭をひねる問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13721

問題

W*Hの長方形の紙がある。
この紙を何度か紙の辺に平行な線で折っていき、最終的に面積をAにしたい。

面積をAにできる最小折り回数を求めよ。

解法

Aが10^5なので、折った後の幅x×高さyは容易に総当たりできる。

x≦Wかつy≦Hならそのような折り方は可能である。
後は何回折ればよいかを求めるだけである。

横線にそって折れば高さだけ減少し、縦線に沿って折れば幅だけ減少する。
よって縦横折った回数を個別に考えて、足し合わせればよい。

そのためここでは横についてWをxにするのに何回折ればよいか考える。
Wを1回折るった後の幅をW'とすると、折り目の位置によってとなるように折れる。
よって以下のようにすればよい。

• W==xならそれ以上折る必要はない。
• x ＜ W ≦ 2*x なら1回折ってxに出来る
• 2*x ＜ Wなら、1回幅をにし、再帰的にW'をxにする回数を求める。

class FoldingPaper2 {
	public:
	int fold(int from,int to){
		if(from==to) return 0;
		if(from<=to*2) return 1;
		return 1+fold((from+1)/2,to);
	}
	int solve(int W, int H, int A) {
		int x;
		int mi=1<<30;
		for(x=1;x<=A;x++) if(A%x==0) {
			ll y=A/x;
			if(x<=W && y<=H) mi=min(mi,fold(W,x)+fold(H,y));
		}
		if(mi>=1<<30) mi=-1;
		return mi;
	}
}

まとめ

前半のx*y列挙パートは新鮮味はないけど、後半の折りたたみ回数パートの考え方は面白いな。
最初は(W+x-1)/x回かと思っちゃったよ。