TCO2012 Round2B - 300 BlurredDartboard - kojingharangの日記

2012-05-12

TCO2012 Round2B - 300 BlurredDartboard

03:43 |

p[i] には 1～N(<= 50) のどれかが重複なく入っていたが、いくつか 0 になっている。適当な p[i] を選んで加算するのを K 回行う。同じのを複数回選んでいい。合計が確実に P(<= 10**9) 以上になるような最小の K を求める問題。

0 のやつを全部加算すると、隠れてる数の合計が確実に加算されることになる
なので、まずできるだけ max(0 のやつの合計, 0 じゃないやつの最大値) を使う。
残りは, 0 じゃないやつの最大値を使うか、0 のやつで最悪の選び方をしたとして小さい方から順に使うかのどちらか。

class BlurredDartboard {
	public:
	int minThrows(vector <int> p, int P) {
		int N=p.size();
		
		VI vis(N, 0);
		int ma=-1;
		REP(i, N) {
			if(p[i]>0) {
				vis[p[i]-1]=1;
				ma=max(ma, p[i]);
			}
		}
		VI hid;
		REP(i, N) if(vis[i]==0) hid.PB(i+1);
		int hidsum = accumulate(ALL(hid), 0);
		sort(ALL(hid));
		
		int ans=0;
		if(ma==-1 || hidsum > ma*hid.size()) {
			ans += P/hidsum*hid.size();
			P -= P/hidsum*hidsum;
		} else {
			ans += P/ma;
			P -= P/ma*ma;
		}
		cout<<ans<<" "<<P<<endl;
		if(P==0) return ans;
		
		int lans=0;
		int PP=P;
		REP(i, hid.size()) {
			PP-=hid[i];
			lans++;
			if(PP<=0) break;
		}
		if(PP>0) lans = 10000;
		cout<<lans<<endl;
		if(ma!=-1) lans = min(lans, (P+ma-1)/ma);
		cout<<lans<<" "<<ma<<endl;
		
		return ans+lans;
	}
};