Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@ZhangChaoran

AtCoder Beginner Contest 153

More than 1 year has passed since last update.

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)
0
Help us understand the problem. What is going on with this article?
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.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?