kmjp's blog

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

TopCoder SRM 756 Div1 Easy Div2 Hard NewBanknote

不参加でした。出てたら解けてたかなぁ…。
https://community.topcoder.com/stat?c=problem_statement&pm=15439

問題

コインの種類が標準で1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000があるとする。
ここに1種類追加でNの価値のコインが追加されたとしよう。

金額Aをちょうど支払うのに最小何枚のコインが必要か。
Aは2*10^9以下とする。

解法

元のコイン群だけを使う場合、貪欲に高いコインを優先的に使うのが良いので、必要コイン数は容易にわかる。

価値Nのコインを50000枚以上使うことはないので、Aのコインの使用量を0~50000で総当たりしよう。
Nが50000以下なら、このコインを50000枚使うなら価値50000のコインをN枚使った方がよい。
また、Nが50000以上ならA/Nは40000以下なので、やっぱり50000枚以上使うことはない。

class NewBanknote {
	public:
	int how(int a) {
		int ret=0;
		vector<int> V={50000,20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1};
		FORR(v,V) ret+=a/v, a%=v;
		return ret;
	}
	int hoge(int N,int A) {
		int mi=1<<30;
		int i;
		FOR(i,50000) if(1LL*N*i<=A) mi=min(mi,i+how(A-N*i));
		return mi;
		
	}
	
	vector <int> fewestPieces(int newBanknote, vector <int> amountsToPay) {
		vector<int> R;
		FORR(a,amountsToPay) R.push_back(hoge(newBanknote,a));
		return R;
	}
}

まとめ

実際こんな最小から最高まで50000倍も異なるコイン・紙幣使う国ってあるのかね?