TopCoder SRM 649 Div2 Medium CartInSupermarketEasy

Div1 Hardを大幅に簡単にした問題だが、こちらを解いておくとDiv1 Hardの考え方がすっきりする。
http://community.topcoder.com/stat?c=problem_statement&pm=13659

問題

初期状態でN個のカートからなる列が1つだけある。
１ターン毎に、カート列群に対しそれぞれ以下の何れかの行動をどちらか１つ行える。

• 列のカートを１つ減らす
• 列を２つに分割する（分割後の２列のカート数配分は任意）

ただし、列の分割は最大K回までしか行えない。
全てのカートを取り除くのにかかる最小ターン数を答えよ。

解法

列を１回分割すると、以後列のカートを減らすペースを１増加できる。
よって、どうせ分割するなら早めに行った方がよい。

そのため最大X列まで分割するケースを考える。
とする。たとえばX=6ならY=3。
この場合、最初の(Y-1)ターンはひたすら列の分割を行う。
Yターン目は(X-2^(Y-1))列は分割し、残り(2^Y-X)列は１個減らすと、X列になる。
あとはYターン目に残った(N - (2^Y-X))個のカートを１ターンX個減らすので、最初のYターンと合わせて必要ターン数はとなる。

列の分割が最大K回なので、X=1～(K+1)に対し上記値の最小値を求めればよい。

class CartInSupermarketEasy {
	public:
	int calc(int N, int K) {
		int mi=N;
		for(int X=1;X<=K+1;X++) {
			int y=0;
			while(1<<y<=X) y++;
			if(X>N) continue;
			
			mi=min(mi,(N-(1<<y)+X-1)/X+(y+1));
		}
		return mi;
	}
}

まとめ

ここまで考察するとDiv1 Hardが楽。