TopCoder SRM 774 : Div1 Easy Div2 Hard LandSplitter

一応レート増で済んでよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15869

問題

整数Nをいくつかに分裂させる。
今値(X+Y)を正整数XとYに分割させるとコストがX*Yかかるとする。
Nをいくつかの正整数に分裂させる際、最終的にすべてA以上B以下になるようにしたい。
最小コストを求めよ。

解法

このパターンの問題は過去SRMでちょこちょこ出ているが、分割順は最終的なコストに関係ない。
最終的に分割した要素Pがあるとすると、P(N-P)/2だけコストに加算されると考えるとよい。
そうすると、できるだけ大きな要素を作るように分割するのが最良である。

以下のコードでは、分割数を総当たりし、その範囲でできるだけ大きな要素を作らせた場合のコストを計算している。

class LandSplitter {
	public:
	long long cheapest(int N, int A, int B) {
		ll mi=1LL<<60;
		
		for(ll i=1;1LL*A*i<=N;i++) {
			ll a=1LL*i*A;
			ll b=1LL*i*B;
			
			if(a<=N&&N<=b) {
				ll pat=0;
				if(A==B || b==N) {
					pat=1LL*B*(N/B)*(N-B);
				}
				else {
					ll lef=N-a;
					int nb=lef/(B-A);
					pat+=1LL*nb*B*(N-B);
					pat+=1LL*(A+(lef%(B-A)))*(N-(A+(lef%(B-A))));
					pat+=1LL*(i-nb-1)*A*(N-A);
				}
				mi=min(mi,pat);
			}
			
		}
		if(mi==1LL<<60) return -1;
		mi/=2;
		return mi;
	}
}

まとめ

最初均等割りが最良と勘違いしてタイムロスしてしまった。