kmjp's blog

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

Zepto Code Rush 2015 : C. Om Nom and Candies

Zepto Code Rushに参加。
yukicoderのおかげもあってABCDを解き、レート微増。
http://codeforces.com/contest/526/problem/C

問題

赤い飴は重さWr、おいしさHrである。
青い飴は重さWb、おいしさHbである。

重さの合計がC以下の範囲で両方の飴を好きな数(もちろん非負整数)食べられるとき、おいしさの総和の最大値を答えよ。

解法

つい最近、Wr,Wbが1のケースをやったね。
yukicoder : No.176 2種類の切手 - kmjp's blog

Wrの方がWbより大きいとする。
この場合赤い飴はH/Wr個以下しか食べられない。

よってWrが十分大きい(1000以上)の場合、赤い飴の数を0~(H/Wr)個まで総当たりし、それぞれ対応する青い飴の最大数を求めておいしさの最大値を求めればよい。

Wrが小さい場合、上記記事のLCMの議論を参考にすると、赤い方は0~Wbの範囲で総当たりすれば良いことがわかる。
Wb≦WrなのだからWbは1000以下であり、処理時間は問題ない。

ll C,HR,HB,WR,WB;
ll ma;

void solve() {
	int i,j,k,l,x,y; string s;
	ll r,b;
	
	cin>>C>>HR>>HB>>WR>>WB;
	FOR(i,2) {
		if(WR>=1000) {
			FOR(r,C/WR+1) ma=max(ma,r*HR+(C-r*WR)/WB*HB);
			cout<<ma<<endl;
			return;
		}
		swap(HR,HB), swap(WR,WB);
	}
	
	ll lcm=min(C,WB*WR/__gcd(WB,WR));
	FOR(r,lcm/WR+1) ma=max(ma,r*HR+(C-r*WR)/WB*HB);
	FOR(b,lcm/WB+1) ma=max(ma,b*HB+(C-b*WB)/WR*HR);
	
	cout<<ma<<endl;
}

まとめ

yukicoderのヒット率最近高いなぁ。