TopCoder SRM 527 Div2 Hard P8XCoinChangeAnother

さっきのSRM526.5に比べると、こちらは普通の問題。
Codeforcesに出てきそう。
http://community.topcoder.com/stat?c=problem_statement&pm=11222

問題

N種類の硬貨があり、それぞれの価値は2^0,2^1, ... , 2^(N-1)である。
これらの硬貨を計C枚用いて価値Sぴったりにすることができるか。

できるなら、各硬貨の枚数を並べたとき辞書順最小となるような組み合わせを答えよ。

解答

まず、価値Sを2進数表記するとSを構築する最少の硬貨枚数を得ることができる。
ただし、2^N以上の価値の硬貨はないので、その分は2^(N-1)の価値の硬貨をたくさん持つことで対応する。

2^iの硬貨を2^(i-1)の硬貨２枚に両替することで、総価値を変えずに枚数を１枚増やすことができる。
よって、枚数がCに到達するまで上位の硬貨を下位の硬貨に両替していけばよい。

class P8XCoinChangeAnother {
	public:
	vector<long long> solve(int N, long long coins_sum, long long coins_count) {
		int bc=__builtin_popcountll(coins_count);
		int i;
		if(bc>coins_count) return vector<long long>();
		if(coins_count>coins_sum) return vector<long long>();
		
		vector<ll> R(N,0);
		FOR(i,N) R[i]=coins_sum%2, coins_sum/=2;
		R[N-1]+=2*coins_sum;
		FOR(i,N) coins_count -= R[i];
		if(coins_count<0) return vector<long long>();
		
		for(i=N-1;i>=1;i--) {
			if(coins_count==0) break;
			ll mi=min(coins_count,R[i]);
			R[i]-=mi;
			R[i-1]+=mi*2;
			coins_count-=mi;
		}
		
		return R;
	}
};

まとめ

これはDiv1 Easy、Div2 Mediumクラスの問題では。