はまやんはまやんはまやん

hamayanhamayan's blog

Many Balls [AtCoder Beginner Contest 216 C]

https://atcoder.jp/contests/abc216/tasks/abc216_c

関連知識

解説

https://atcoder.jp/contests/abc216/submissions/25449969

この問題は2進法についての理解があると解法が思いつきやすい。
このような構築問題は方針がいくつかあるが、Nを見ると計算量的にlogNでやらないとという感じがあるので、
このあたりから2進法が分かっていなくても解けるのかもしれない。
2進法についてはググって調べてきてほしいが、知らなくても解説は読める(はず)

操作を逆に見てみる

合計120回とあるが、とりあえず最適っぽい方針も立てられないと前進しない。
今回は実は操作を逆に見てみることで方針が立てやすくなる。
つまり、魔法Aを使うと-1されて、魔法Bを使うと÷2されることになる。

5 -A-> 4 -B-> 2 -B-> 1 -A-> 0

のような感じになるが、これは丁度順番を逆転させると元の問題に帰着される。
なので、NをA,Bの操作をして0になる様にやっていこう。

構築問題のルールはシンプルに

構築問題に共通で言えるアドバイスとして、なるべくシンプルなルールを採用することである。
複雑だと大体バグるし、ちょっと踏みとどまってシンプルなルールを探す方が期待値が高いことが多い(体験上)。
よって、シンプルなルールを考える。
以下のルールで今回はACできる。

  • 2で割り切れない場合は魔法Aをやる(魔法Aをやるしかないけど)
  • 2で割り切れる場合は魔法Bをやる

再掲すると、

5 -A-> 4 -B-> 2 -B-> 1 -A-> 0

これはこのルールで作られている。
どんな数であってもこのルールを適用することで0になることが分かるだろう。
答える前に魔法の打ち方を反転させるのを忘れずに。

120回に収まるのか?

なるべく回数を抑えるためには魔法Bを多く使うことが重要になる。
今回の方針で重要なのは魔法Aが連続することはないという部分である。
魔法Aをやれば必ず2で割り切れる状態になるので最低2回に1回は魔法Bが行える。
魔法Bを1回やれば2分の1以下にできるし、2回やれば4分の1以下にできるし、3回やれば8分の1以下である。
極端に小さくなっていくことが分かると思う。
実際はlogNになるというか、2進法のビット数分になるというか、具体的には60回くらいで0にできる。
で、毎回魔法Aを挟んでも120回くらいになって間に合うという見積もりである。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    string ans = "";
    while (1 <= N) {
        if (N % 2 == 1) {
            ans += "A";
            N--;
        }
        else {
            ans += "B";
            N /= 2;
        }
    }
    reverse(all(ans));
    cout << ans << endl;
}