Google Code Jam 2015 Qualification Round : B. Infinite House of Pancakes

前もこれ系のミスやらかしたことある…。
https://code.google.com/codejam/contest/6224486/dashboard#s=p1

問題

無限の人がそれぞれ皿の前にいる。
そのうちD人の皿にはP[i]個のパンが入っている。

店員は１分毎に以下の行動を取れる。

• 店員が何もしないと、自分のさらにパンが入っている人は皆１個ずつパンを食べる。
• 店員は誰か１人のパンの一部を他の人の皿に移せる。この場合この１分は誰もパンを食べない。

店員は早く全員のパンを空にしたい。
最適に行動した場合、最短で何分でパンを空に出来るか。

解法

パンを食べるのにかける時間xを総あたりする。
すなわち、先にxを定めて、xより多くのパンを持つ人がいたらそれらを他人に移すようにする。
パンを持つ人が多いほど減少速度が上がるので、パンを移す行動は最初にすべて行うべきである。

xより多いパンを持つ人がいたら、１分にx個他の人にパンを移すと考えると、パンを空にする総時間はである。
上記式を各xについてもとめ、最小値を出せばよい。

int D,P[1010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>D;
	FOR(i,D) cin>>P[i];
	
	int mi=50000;
	for(i=1;i<=1000;i++) {
		int step=0;
		FOR(x,D) step += (P[x]+i-1)/i-1;
		mi=min(mi,step+i);
	}
	
	_P("Case #%d: %d\n",_loop, mi);
}

まとめ

最初xずつにするんじゃなくて、半々に分けていって失敗。
以前もCodeforcesで似たようなミスしたことある…。