kmjp's blog

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

Google Code Jam 2015 Round 1C : C. Less Money, More Problems

前の問題の影響で、最初タイトルをMonkeyと読み間違えた。
https://code.google.com/codejam/contest/4244486/dashboard#s=p2

問題

この国にはD種類のコインがあり、それぞれの金額がA[i]とする。
この国では、金銭の支払いに際し1種類のコインは最大C枚までしか使えない。

これらのコインで、1~Vのすべての金額を1刻みで支払えるようにしたいが、これらのコインでは不足するかもしれない。
Cは増やすことができないので、コインの種類を増やして対応することにした。

増やさなければならない最小のコインの種類の数を答えよ。

解法

現在のコインで支払えない最小の額が存在する場合、その額のコインを増やせばよい。
A[1]~A[D]のうちA[1]~A[x]で払える金額の最大値はC*(A[1]+...+A[x])である。
この最大値がA[x+1]-1未満である場合、C*(A[1]+...+A[x])とA[x+1]の間に払えない金額が存在するので、C*(A[1]+...+A[x])+1の金額のコインを足していけば良い。

以下のコードでは、以下の工夫をしている。

  • 金額1のコインは無条件に追加
  • 金額(V+1)のコインを番兵代わりに追加
ll C,D,V;
vector<int> P;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>C>>D>>V;
	P.clear();
	FOR(i,D) cin>>x, P.push_back(x);
	if(P[0]!=1) P.push_back(1);
	P.push_back(V+1);
	
	while(1) {
		sort(ALL(P));
		
		ll tot=0;
		FOR(x,P.size()-1) {
			tot += P[x]*C;
			if(tot+1<P[x+1]) break;
		}
		if(tot+1>V) break;
		P.push_back(tot+1);
	}
	
	_P("Case #%d: %d\n",_loop,P.size()-D-1);
}

まとめ

面白い問題でした。