読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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

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

問題

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

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

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

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

解法

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

xより多いパンを持つ人がいたら、1分にx個他の人にパンを移すと考えると、パンを空にする総時間は \displaystyle x + \sum_i \lceil \frac{P_i - x}{x} \rceilである。
上記式を各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で似たようなミスしたことある…。

広告を非表示にする