けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 153 D - Caracal vs Monster (灰色, 400 点)

こういうのだったら、愚直な再帰関数がバッチリはまる!!!

問題へのリンク

問題概要

体力  n のモンスターに魔法を唱えたとき

  •  n = 1 ならば、モンスターは倒れる
  •  n \gt 1 ならば、モンスターは体力が  n/2 (小数点切り捨て) の 2 体のモンスターに分裂する

最初は体力が  H のモンスターが 1 体いる。モンスターがすべて倒された状態になるのに必要な魔法回数の最小値を求めよ。

制約

  •  1 \le H \le 10^{12}

考えたこと

魔法回数の「最小値」といってはいるけど、結局回数はどうやっても同じになる。そして、この問題を見ていると自然に再帰関数を実装したくなると思う。

long long rec(long long N) {
    if (N == 1) return 1;

    // 2 体に分裂するのに「+1」、N/2 を 2 体倒すのに rec(N/2)*2
    return rec(N/2) * 2 + 1;
}

そして rec(H) を呼び出せば OK。再帰関数による計算量爆発事情を聞いたことのある方は、こういう再帰関数の計算量は大丈夫かと怖くなるかもしれない。

しかし今回は大丈夫。むしろ超高速!!!!!
再帰が 1 回進むごとに、引数  N が半減していくのだ。たとえば  H = 256 であったら

256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

という風に減っていく。よって計算量は  O(\log{H}) となる。その理由は「二分探索は毎回探索範囲が半減するから計算量が log になる」というのと一緒だ。

#include <iostream>
using namespace std;

long long rec(long long N) {
    if (N == 1) return 1;
    return rec(N/2) * 2 + 1;
}

int main() {
    long long N;
    cin >> N;
    cout << rec(N) << endl;
}