AtCoder Beginner Contest 153

D - Caracal vs Monster

再帰関数で高速にできる。

import sys
sys.setrecursionlimit(1000000)


def solve(n):
    if n == 1:
        return 1
    return 1 + 2 * solve(n // 2)


print(solve(int(input())))

E - Crested Ibis vs Monster

2つ方法がある。
一つは、解説によるHPごとに魔力消耗を計算する方法です。

import numpy as np
import sys
read=sys.stdin.read

h, n, *ab = map(int, read().split())
a = np.array(ab[::2])
b = np.array(ab[1::2])

magic = np.zeros(h + 1, dtype=np.int64)
for i in range(1, h + 1):
    magic[i] = np.min(magic[np.maximum(i - a, 0)] + b)
print(magic[h])

もう一つは、重複計算をキャッシュで保存するPythonのliblru_cacheを利用する。
ちょっとずるいと感じる。

import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

H, N = map(int, input().split())
AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))


@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    best = float("inf")
    for a, b in AB:
        val = b + f(h - a)
        if val < best:
            best = val
        else:
            break
    return best


AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
bestA, bestB = AB[0]
print(f(H))

F - Silver Fox vs Monster

要するにpop_leftできるdequeを使うと便利です。lru_cacheを知らなかったら、問題Eより簡単だったと思う。

import sys
from collections import deque
read = sys.stdin.read
readline = sys.stdin.readline

n, d, a = map(int, readline().split())
m = map(int, read().split())
monsters = sorted(zip(m, m), key=lambda x: x[0])

bomb_area = deque([])
bomb_power = deque([])
total_damage = 0
ans = 0
for pos, hp in monsters:
    while bomb_area:
        area = bomb_area[0]
        if area < pos:  # 前回の爆弾が今回のモンスターに攻撃しなかった
            bomb_area.popleft()
            power = bomb_power.popleft()
            total_damage -= power  # 届かなかったダメージを減算
        else:
            break
    if hp <= total_damage:
        continue
    else:
        rest = hp - total_damage
        count = rest // a + (rest % a != 0)  # 割り切れるなら商、ないなら商+1
        ans += count
        power = a * count
        total_damage += power
        bomb_area.append(pos + 2 * d)
        bomb_power.append(power)
print(ans)