今年は1Aで抜けられたので、1Bは練習のみ。
こちらは途中A-Largeでミスもあったけど、最終的には全部自力で解けたのでこちらでもRound1は抜けられてたな。
https://code.google.com/codejam/contest/2434486/dashboard#s=p0
問題
N個の整数列M[i]とプレイヤーの初期値Aが与えられる。
M中にプレイヤーの値より小さい数値があれば、その値を取り除き、プレイヤーの値に加算する。
このとき、必要ならば以下のいずれかの処理を行うことができる。
- 特定の値をMに追加する
- 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)); }
まとめ
最初メモ化再帰とか色々したけど、結局かなりシンプルなコードで回答できた。