Help us understand the problem. What is going on with this article?

AtCoder Beginner Contest 153

https://atcoder.jp/contests/abc153

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)
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした