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

Community
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つ方法がある。

``````import numpy as np
import sys

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のlib`lru_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

``````
import sys
from collections import deque

n, d, a = map(int, readline().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