ABC153D Caracal vs Monster

問題

https://atcoder.jp/contests/abc153/tasks/abc153_d

方針

計算量の都合上、シミュレーションを行うことはできない。
数学的な解法を考える。

ポイント

言葉だけで理解しようとするのは若干難しいため、記事の最後にあるシミュレーションを眺めながら読み解いていただきたい。

• 攻撃をすると、モンスターは体力が1でない限り倍々に増えていくためモンスターの数は常に2の累乗である。
  • つまり、攻撃の総回数はそれらの和であるため、2^N-1で表すことができる。
• 攻撃効率がもっとも良いのは攻撃のたびにモンスターの体力の和が攻撃前より1減ることである。
  • 全ての攻撃が効率がよくるのは、Hが2^N-1の場合であるとわかる。
  • また、攻撃回数がモンスターの体力Hを上回ることはない。
• そのため、2^N-1を満たす自然数を小さい順に数え、H以上の値が現れた時、その値が答えである。

コード

H = int(input())
for i in range(41):
    if (2**i-1 >= H):
        print (2**i-1)
        break

シミュレーション

下記のようなシミュレーション用のコードを書いてみた。

ls = [int(input())]
while(ls): # リストの要素が1以上であればtrue
    print (ls)
    new = []
    for e in ls:
        if e>1: # 体力が１であれば、新たなモンスターは出現しない
            new.extend([e//2, e//2])
    ls = new

>>> 6
[6]
[3, 3]
[1, 1, 1, 1]

>>> 7
[7]
[3, 3]
[1, 1, 1, 1]

>>> 8
[8]
[4, 4]
[2, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 1]