SRM 527 Div2 Hard P8XCoinChangeAnother
問題
http://apps.topcoder.com/stat?c=problem_statement&pm=11222&rd=14552
のコインを枚使ってcoins_sumにしたい。かつそのとき使用するコインの枚数の合計としたい。このような辞書式最小のを返せ。
やりかた
coins_sumを2進数で表現したとき、これは2^iのコインを使用する枚数の表現そのものになる。今回はのN桁しか使用することができないのでcoins_sumをN-1桁までは2進数で表現して、N桁以上のものはそのままにしておく。あとは上位桁のコインから貪欲にmin((coins_count - 現在使用しているコインの枚数), 今注目している桁のコイン枚数)を下位の桁に2倍して足していくという作業を繰り返していく。使用しているコインの枚数が途中でcoins_countより大きくなったり、最終的に異なっていたりしたら達成不可能となる。
以下ソース。
class P8XCoinChangeAnother { public: vector<long long> solve(int N, long long coins_sum, long long coins_count) { vector<ll> ret(N, 0); ret[0] = coins_sum; for(int i = 0; i + 1 < N; i++){ ret[i + 1] = ret[i] / 2LL; ret[i] %= 2LL; } ll rem; for(int i = N - 1; i > 0; i--){ rem = coins_count - accumulate(ALL(ret), 0LL); if(rem < 0) return vector<ll>(); if(rem == 0) break; ll n = min(rem, ret[i]); ret[i - 1] += (ll)(2LL * n); ret[i] -= n; } if(coins_count != accumulate(ALL(ret), 0LL)) return vector<ll>(); return ret; } }
やりかたはすぐにわかったが、変な2進数化でかいていたら、それが遠因でWA。シンプルにN桁まで計算するやり方に変えてAC。
ほんとうにだれてるなあ。
Get up! 明日のSUPER ST@R!