kmjp's blog

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

Google Code Jam 2018 Round1A : B. Bit Party

本番こっちの方が楽に通せた。
https://codejam.withgoogle.com/2018/challenges/0000000000007883/dashboard/000000000002fff6

問題

C個のレジのうち最大R個を使って計B個の商品を買う。
各レジiは3つのパラメータM[i],P[i],S[i]で定められる。

M[i]はそのレジで買える最大商品数、P[i]は購入手続きの時間、S[i]は商品1個あたりのスキャンにかかる時間である。
最適なレジの選択をしたとき、B個の商品を買う最短時間を求めよ。

解法

時間で二分探索すればよい。
時間を決めれば各レジで返る商品数が決まるので、上位R個を利用する。

int T,testcase;
int R,C;
ll B;
ll M[1010],S[1010],P[1010];

ll ok(ll v) {
	int i;
	vector<ll> c;
	FOR(i,C) {
		if(v<P[i]) continue;
		c.push_back(min(M[i],(v-P[i])/S[i]));
	}
	sort(ALL(c));
	reverse(ALL(c));
	ll tot=0;
	FOR(i,min((int)c.size(),R)) tot+=c[i];
	return tot>=B;
}

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>R>>B>>C;
	FOR(i,C) {
		cin>>M[i]>>S[i]>>P[i];
	}
	
	ll ret=(1LL<<60)-1;
	for(i=59;i>=0;i--){
		if(ok(ret-(1LL<<i))) ret-=1LL<<i;
	}
	
	
	_P("Case #%d: %lld\n",TC,ret);
}

まとめ

これは定番テクだね。