diverta 2019 Programming Contest 2 : D - Squirrel Merchant

こういう問題、解くことはできても思いつくことはできる自信がないな…。
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_d

問題

ドングリが貨幣の代わりに使える町において、以下のような売買ができるとする。なお、売買は整数グラム単位でなければならない。
また、借金はできないので手持ちのドングリ以上の金属は購入できない。

• 店Aでは、1gの金・銀・銅がドングリGa、Sa、Ba個で売買できる。
• 店Bでは、1gの金・銀・銅がドングリGb、Sb、Bb個で売買できる。

店A→店B→店Aの順で訪問するとき、最適な売買を行うと手持ちのドングリを最大何個に増やせるか。

解法

最大化したいのはドングリなので、金属を残す理由はない。
よって、最適戦略は以下のようになる。

• 店Aより店Bの方が売買価格が大きい金属は、まずAで購入してBを全売りする
• 店Bより店Aの方が売買価格が大きい金属は、まずBで購入してAを全売りする

よって売る場合は常に全売りなので、あとは何を何個買うかを考えよう。
その際は、店Aと店Bの金額の大小の様子によって変わる。

• 全金属店Aより店Bの方が売買価格が高い
  • 店Aで、金・銀を買う個数を総当たりしよう。残金は銅を全買いし、全部を店Bで売ることにする。計算量はO(N^2/(Ga*Sa))。
• 全金属店Bより店Aの方が売買価格が高い
  • 店Bで、金・銀を買う個数を総当たりしよう。残金は銅を全買いし、全部を店Aで売ることにする。計算量はO(N^2/(Ga*Sa))。
• 店Aより店Bの方が売買価格が高い金属が2つ
  • 仮に金銀が店Aの方が安く、銅はAの方が高いとする。
  • この場合、店Aで、金・銀を買う個数を総当たりしよう。その後、店Bで金銀を売った後全額銅を買い、再びAで銅を売る。計算量はO(N^2/(Ga*Sa))。
• 店Aより店Bの方が売買価格が高い金属が1つ
  • 仮に金が店Aの方が安く、銀銅はAの方が高いとする。
  • この場合、店Aでは金を全買いし、店Bでそれを売る。その後銀を買う量を総当たりしよう。残金は銅を買い、銀と銅は店Aで売る。
  • 金の売買の結果、店Bでは最大で残金が一時O(N*Gb)となる。ただしその後の総当たりが銀だけでよいので、計算量はO(N*Gb/Sb)となり間に合う。

int N;
ll G[2],A[2],B[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2) cin>>G[i]>>A[i]>>B[i];
	
	if(G[0]>=G[1] && A[0]>=A[1] && B[0]>=B[1]) {
		swap(G[0],G[1]);
		swap(A[0],A[1]);
		swap(B[0],B[1]);
	}
	
	ll ret=N;
	if(G[0]<=G[1]&&A[0]<=A[1]&&B[0]<=B[1]) {
		for(x=0;x<=N;x+=G[0]) {
			for(y=0;x+y<=N;y+=A[0]) {
				int z=(N-x-y)/B[0]*B[0];
				ll cur=(N-x-y-z)+x/G[0]*G[1]+y/A[0]*A[1]+z/B[0]*B[1];
				ret=max(ret,cur);
			}
		}
	}
	else {
		if(G[0]>=G[1]&&A[0]<A[1]) swap(G[0],A[0]),swap(G[1],A[1]);
		if(A[0]>=A[1]&&B[0]<B[1]) swap(B[0],A[0]),swap(B[1],A[1]);
		if(G[0]>=G[1]&&A[0]<A[1]) swap(G[0],A[0]),swap(G[1],A[1]);
		
		
		if(A[0]<A[1]) {
			for(x=0;x<=N;x+=G[0]) {
				for(y=0;x+y<=N;y+=A[0]) {
					ll cur=(N-x-y)+x/G[0]*G[1]+y/A[0]*A[1];
					ll v=cur/B[1];
					cur=cur%B[1]+v*B[0];
					ret=max(ret,cur);
				}
			}
		}
		else {
			ll v=N/G[0];
			ll cur=N%G[0]+v*G[1];
			for(x=0;x<=cur;x+=A[1]) {
				y=(cur-x)/B[1]*B[1];
				ll ncur=(cur-x-y)+x/A[1]*A[0]+y/B[1]*B[0];
				ret=max(ret,ncur);
			}
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

ドツボにはまると1時間持って行かれそうな問題。
ちょっと苦戦したけどどうにか解けて良かった。