ABC153 D - Caracal vs Monster

問題原文

atcoder.jp

問題要旨

体力が のモンスターがいる。モンスターが全滅するまで、以下の操作を繰り返す。

• モンスター一体を倒す。このとき、倒したモンスターの体力が１より大きければ、その半分の体力を持つモンスターが２体増える。（小数点以下切り捨て）

何回操作が行われるか求めよ。

• 

解法

分岐の仕方を図示すると、完全二分木のようになっていることがわかる。

完全二分木の要素数は、木の高さに依存し、木の高さは、 数を二進表記したときの長さになる。

実装

bit_length() 便利。

H = int(input())
print(2 ** (H.bit_length()) - 1)

感想

完全二分木とbitの関係はパッと引き出せるようになっておくぞ。