1. ZhangChaoran

    Posted

    ZhangChaoran
Changes in title
+AtCoder Beginner Contest 153
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,114 @@
+https://atcoder.jp/contests/abc153
+
+###D - Caracal vs Monster
+
+再帰関数で高速にできる。
+
+```python
+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ごとに魔力消耗を計算する方法です。
+
+```python
+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のlib`lru_cache`を利用する。
+ちょっとずるいと感じる。
+
+```python
+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より簡単だったと思う。
+
+```python
+
+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)
+```