kmjp's blog

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

Google Code Jam 2013 Round 1B : A. Osmos

今年は1Aで抜けられたので、1Bは練習のみ。
こちらは途中A-Largeでミスもあったけど、最終的には全部自力で解けたのでこちらでもRound1は抜けられてたな。
https://code.google.com/codejam/contest/2434486/dashboard#s=p0

問題

N個の整数列M[i]とプレイヤーの初期値Aが与えられる。
M中にプレイヤーの値より小さい数値があれば、その値を取り除き、プレイヤーの値に加算する。
このとき、必要ならば以下のいずれかの処理を行うことができる。

  1. 特定の値をMに追加する
  2. Mの値を1つ取り除く

Mのすべての値を取り除くまでに、必要な上記処理の最小回数を答える。

解法

まずMを昇順にソートしておく。

※プレイヤーの値Aに対し、M中でAより小さい物を取り除いてAに加算していく。
MにAより大きい値が残った場合、

  • Mに(A-1)を追加する処理を1回行う。この場合Aを2*A-1として※以降の処理を再帰的に実行する。
  • 残されたMの要素を、要素数回処理を行って消す。

A=1の時は(A-1)を足しても要素が増えず無限ループになるので注意。
A=1の時は前者は取れない。

int N,A;
int M[1001];

int calc(int CM,int L,int R) {
	while(CM>M[L] && L<R) CM+=M[L++];
	if(L>=R) return 0;
	
	if(CM==1) return R-L;
	return min(1+calc(CM+(CM-1),L,R),R-L);
}

void solve(int _loop) {
	int i,j,x,y,ne=0;

	GET2(&A,&N);
	FOR(i,N) M[i]=GETi();
	sort(M,M+N);
	
	_PE("Case #%d: %d\n",_loop,calc(A,0,N));
}

まとめ

最初メモ化再帰とか色々したけど、結局かなりシンプルなコードで回答できた。