TopCoder SRM420 Div1Hard

問題

何種類かの硬貨がたくさんあり、それぞれ額面が決まっている。常に1単位硬貨が存在する。
ある両替機は、いくらかのお金(2単位以上)を受け付けて、次の規則で両替する。
「2枚以上の硬貨に両替する。但し、枚数は可能な限り少なくする。枚数が同じときは、降順に硬貨の額面を並べた時、辞書順最大のものにする。」
この両替機を使って、ある金額をすべて1単位硬貨にしたい。最初にある金額を投入し、そのあとは出てきた硬貨を投入する。何回投入しないといけないか。

解法

金額がとても大きいのが問題だが、硬貨はどれも1000単位以下である。
ここで、100万単位以上については「100万以下になるまで、最大の硬貨を出す」戦略が使えることがわかる。
すると、金額の上限を100万とみなすことができ、100万は小さいのでDPやるだけである。

コード

#include <vector>

using namespace std;

class ChangeOMatic
{
	vector<int> coins;
	int dpA[1002001], dpB[1002001], fromA[1002001], fromB[1002001];
	int cost[50];
public:

	long long calc(int V)
	{
		if(V==0) return 0;
		long long ret = 1;
		
		ret += cost[fromB[V]];
		V -= coins[fromB[V]];
		while(true){
			if(fromA[V]<0) break;
			ret += cost[fromA[V]];
			V -= coins[fromA[V]];
		}
		return ret;
	}
	
	long long howManyRounds(vector<int> out, long long in)
	{
		coins = out;
		
		dpA[0] = 0;
		dpB[0] = 0;
		fromA[0] = -1;
		fromB[0] = -1;
		dpA[1] = 1;
		dpB[1] = 1;
		fromA[1] = -1;
		fromB[1] = -1;
		for(int i=2;i<=1002000;i++){
			dpA[i] = 1002002;
			dpB[i] = 1002002;
			fromA[i] = -1;
			fromB[i] = -1;
			for(int j=coins.size()-1;j>=0;j--){
				if(i >= coins[j]){
					if(dpA[i] > 1+dpA[i-coins[j]]){
						dpA[i] = 1+dpA[i-coins[j]];
						fromA[i] = j;
					}
				}
				if(i > coins[j]){
					if(dpB[i] > 1+dpA[i-coins[j]]){
						dpB[i] = 1+dpA[i-coins[j]];
						fromB[i] = j;
					}
				}
			}
		}
		
		cost[0] = 0;
		for(int i=1;i<coins.size();i++){
			cost[i] = 1;
			int t = coins[i];
			
			cost[i] += cost[fromB[t]];
			t -= coins[fromB[t]];
			while(true){
				if(fromA[t]<0) break;
				cost[i] += cost[fromA[t]];
				t -= coins[fromA[t]];
			}
		}
		
		long long mn = max((in - 1000000)/coins[coins.size()-1], 0LL);
		return calc((int)(in-mn*coins[coins.size()-1])) + mn*cost[coins.size()-1];
	}
};