ABC153 D - Caracal vs Monster
備忘録
問題
回答
import sys import os import math import string ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: x * y / math.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def f(N): atk = 0 if N == 1: atk += 1 else: atk += f(N // 2) * 2 + 1 return atk def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() print(f(N)) if __name__ == '__main__': main()
考え方
モンスターの体力N
が1
の場合は攻撃回数1
、
モンスターの体力N
が2
以上の場合には、
攻撃回数1
+ 体力がN//2
のモンスター2体を倒すために必要な攻撃回数を返す関数を作る。
具体的な実装は再帰関数で行うことができる。
はじめは体力の最大値が10e12
のため、計算量でTLE
になるかと思ったが、
再帰を行うたびに体力が半分になるため、計算量は思ったよりも少ない。
(感覚的には二分探索みたいな感じ)