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; }