TopCoder SRM 669 Div1 Easy SubdividedSlimes

ありがちな罠に引っかからなくてよかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13946

問題

サイズSのスライムがいる。
各スライムは、２つの正整数のサイズx,yのスライムに分割することができる。その際、x*yのポイントを得られる。
スライムは（サイズが２以上であれば）何度も分割可能である。

総ポイントMを得るために必要な最小分割回数を求めよ。

解法

Div2 Mediumを解いておくと簡単である。
(p-1)回分割してp個になった場合の各サイズをA[i]とする。
Div2 Mediumでは合体、こちらの問題は分割だが、ポイントの合計値は同様に考察できてとなる。
相加相乗平均の不等式等をもとに考えると、AはSを均等に分割すると有利であることがわかる。
よって、p=2～Nまで順にためし、Sを均等分割してAを作ってみて、ポイント合計値がM以上になるpを求め、p-1を答えればよい。

想定誤解法として、今いるスライムのうち最大のものを２分割するアプローチがある。
これだとS=9,M=27がチャレンジケースの一例で、9→{3,3,3}と分割するとポイント合計値は27になるが、9→{4,5}→{4,2,3}とすると合計値が26で分割２回で到達できなくなってしまう。

class SubdividedSlimes {
	public:
	
	int needCut(int S, int M) {
		int i,x;
		
		for(i=2;i<=S;i++) {
			int tot=0;
			FOR(x,i) {
				int cur=S/i+(S%i>x);
				tot += cur*(S-cur);
			}
			if(tot/2>=M) return i-1;
		}
		return -1;
	}
}

まとめ

以前SRMで想定誤解法のアプローチをやらかしたことがあったので、うまく回避＋Chal祭りできてよかった。