yukicoder : No.288 貯金箱の仕事

解説見て時事ネタだとわかった。
http://yukicoder.me/problems/333

問題

この国にはN種類の硬貨があり、それぞれの価値はA[i]円である。
ゆきうさぎさんはそれぞれをK[i]枚持っている。

ゆきうさぎさんはM円貯金したい。
その際、残りの手持ちの硬貨の数を最小化したい。
貯金の際にゆきうさぎさんはM円以上のお金を支払うと、お釣りは最小の硬貨となるような組み合わせで返される。

ゆきうさぎさんが貯金のために最適な支払いをしたとき、手持ちの硬貨数を求めよ。

解法

手持ちがM円未満の時は条件を満たせない。

お釣りは最小の硬貨数で貰えるので、とりあえず全額払ってしまうのが良い。
そう考えると、結局(お釣りを返す側が)M円払う最小硬貨数を求める問題になる。

本番考えてたのは、こんな感じ。
「２種類の硬貨A[x],A[y] (A[x]＜A[y])があるとすると、LCM(A[x],A[y])以上の金額を支払うとき、価値の低い方はA[y]枚以下でいいよな。」
「A[N]^2、つまり250,000円ぐらい以下の金額は色んな硬貨を使うとして、残りは１種類の硬貨で全部支払うことができるんだろうな」

そこで、厳密な証明はせず、こんな感じで解いたら解けてしまった。

• 250000円まではDPで支払い方の最小硬貨数を求める。
• 残り支払金額を1種類の硬貨で払うと仮定したとき、何枚の硬貨を使うか計算する。

実際にはEditorialを見ると、鳩ノ巣原理の応用で「残り支払金額を1種類の硬貨で払う」場合その硬貨は最大価値のもので確定するようだ。

int N;
ll M;
int A[501];
ll K[501];
ll can[400000];
ll tot;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>K[i], tot += K[i]*A[i];
	
	if(tot<M) return _P("-1\n");
	M=tot-M;
	
	FOR(i,250001LL) can[i]=1LL<<60;
	can[0]=0;
	
	ll ret=1LL<<60;
	FOR(i,250001) {
		FOR(x,N) if(i-A[x]>=0) can[i] = min(can[i], can[i-A[x]]+1);
		if(i<=M && (M-i)%A[N-1]==0) ret=min(ret,can[i]+(M-i)/A[N-1]);
	}
	if(ret>=1LL<<60) ret=-1;
	cout<<ret<<endl;

}

まとめ

貯金箱シリーズはどちらのWriterさんの問題も毎度勉強になります。