SRM 527 Div2 Hard P8XCoinChangeAnother

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11222&rd=14552
$2^0, 2^1, 2^2, \cdots, 2^{N-1}$ のコインを $a_0, a_1, a_2, \cdots, a_{N-1}$ 枚使ってcoins_sumにしたい。かつそのとき使用するコインの枚数の合計 $\sum_{i = 0}^N a_i = coins count$ としたい。このような辞書式最小の ${\bold{a}}$ を返せ。

やりかた

coins_sumを2進数で表現したとき、これは2^iのコインを使用する枚数の表現そのものになる。今回は $2^0 \sim 2^{N-1}$ の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。

ほんとうにだれてるなあ。