【ABC216】C - Many Balls

atcoder.jp

解法

操作を逆順にして、Nから順に減らしていくことを考える。

• 魔法A: 箱の中からボールを1つ減らす
• 魔法B: 箱の中のボールを1/2にする

という操作に置き換えられる。

Nが奇数のときは魔法Aを使えば必ずNは偶数になるため、次に魔法Bを使うことができるようになる。
このため、Nが制約以上にとてつもなく大きかった場合でも少なくとも60回は2で割れることがわかる。
10¹⁸<2⁶⁰であるため、120回以内でNを0にできることが証明できた。

実装

最後に元の順番に戻すのを忘れないこと。

void solve(long long N) {
    string ans = "";

    REP (i, 120) {
        if (!N) break; // N=0なら終了

        if (N % 2 == 0) {
            N /= 2; // 魔法B
            ans.push_back('B');
        } else {
            N--; // 魔法A
            ans.push_back('A');
        }
    }

    ALL(reverse, ans); // 元の順番にする
    c(ans); // 出力
}