【ABC153 D】「Caracal vs Monster」を解く【Python3】

体力Hのモンスターに、カラカルが勝つまで行う攻撃の回数の最小値を求める問題です。

モンスターの体力が1であるかどうかで、攻撃後の状態が変わります。

提出

h = int(input())
ans = 1

for i in range(1, h):
    ans += 2 ** i
    h = h // 2
    if h == 1:
        break

print(ans)

体力が1でなかった場合、1回攻撃すると2体になり、2体を攻撃すると4体、次は8体となることに注目して、「2のi乗」を体力が1になるまで足していくことで、答えを導けます。

このほか、再帰関数を用いて解くこともできます。

提出

def attack(h):
    if h == 1:
        return 1
    return attack(h//2)*2+1

s = attack(int(input()))
print(s)

分裂させるために1回攻撃するため「+1」、2体をそれぞれ攻撃するため「attack(h//2)*2」を足し合わせたものを返します。

これを体力が1になるまで繰り返します（体力が1の場合は1を返します）。

再帰関数は、その関数自体を返し続ける関数のことです。

再帰関数は最終的に終了条件で終わるようになっています。そのため、状態が変化していき終了条件に近づいていく必要があります。

今回はhが「h//2」によって変化していき、最後には1になります。

【ABC153】解説記事リスト