目次
AtCoder Beginner Contest 153 D～F問題メモ
全問題同一Writerによるコンテストは統一性があってよき。
問題セットは典型問題も多く、競プロが得意なフレンズなら比較的かんたんな回という印象。
D - Caracal vs Monster
問題
- 最初、体力 $H$ のモンスターが1匹いる
- モンスターを1体選んで攻撃する
- モンスターの体力が1なら、モンスターの体力は0になる
- モンスターの体力が2以上なら、体力が $[X/2]$ のモンスター2体に分裂する
- $[r]$ は $r$ を超えない最大の整数を表す
- 全てのモンスターの体力を0以下にするまでに行う必要のある攻撃回数の最小値を求めよ
- $1 \le H \le 10^{12}$
解法
再帰関数。
攻撃1回1回をシミュレートすると、こんな感じで1回の矢印が1回の攻撃を表す。
H=7
7 → 3 → 1 → K.O.
1 → K.O.
3 → 1 → K.O.
1 → K.O.
だが、サンプル3にもあるように、$H=10^{12}$ だと1兆回以上も攻撃せねばならず、間に合わない。
ここでメモ化再帰を行うことを思いつく。 上の例で、体力3のモンスターは途中で2体現れるが、倒すまでにかかる攻撃回数は同じである。 なので、どちらかを計算して「体力3のモンスターを全て倒しきるのにかかる手数は3回」とわかれば、もう1体はその結果を使えばよい。
ただまぁ、これ、よく考えれば同じ $x$ が2回呼ばれることは無いので、メモ化は必要なかった。単なる再帰でよい。
def get_func():
cache = {1: 1}
def f(x):
if x in cache:
return cache[x]
cache[x] = f(x // 2) * 2 + 1
return cache[x]
return f
h = int(input())
f = get_func()
print(f(h))
もっとシンプルな解法
最初の状態から $k$ 回攻撃を加えられたモンスターは、体力 $H/2^k$、数 $2^k$ と決まっているので、$H/2^k=0$ となるはじめての $k$ まで攻撃し、$2^0+2^1+...+2^k$ が答え。
print((1 << int(input()).bit_length()) - 1)
E - Crested Ibis vs Monster
問題
- 体力 $H$ のモンスターが1体いる
- $N$ 種類の魔法攻撃によって体力を0以下にして倒す
- $i$ 番目の魔法を使うと、モンスターの体力を $A_i$ 減らせるが、自身の魔力を $B_i$ 消耗する
- 同じ魔法は何度でも使える
- 消耗する魔力の合計の最小値を求めよ
- $1 \le H \le 10^4$
- $1 \le N \le 10^3$
- $1 \le A_i,B_i \le 10^4$
解法
同じ品物を何度でも採用できるナップサック問題。0-1ナップサックと区別して、個数制限無しナップサックなどと呼ばれる。
- $DP[i][k]=i$ 番目までの魔法だけを使うとして、モンスターの体力をちょうど $k$ 減らすために消耗する魔力の最小値
- 初期化: $DP[0][0]=0$、残りはINF
今回のナップサック問題は、$i$ が1つ前の状態しか更新に使わないので、実装上は $i$ は省略して $k$ のみの1次元配列で持ち、以下のように更新することができる。
- $DP[k+A_i] = \min(DP[k+A_i], DP[k]+B_i)$
$k+A_i$ が配列サイズを超えないよう、大きめに作るか、$k+A_i \gt H$ となったら強制的に $H$ にするかなどする必要がある点に注意。
$k$ の更新の順序が重要で、
- 同じものを1つしか採用できないナップサックなら、$k$ の大きい方から
- いくつでも採用できるナップサックなら、$k$ の小さい方から
埋めていくと、正しく求められる。
Pythonでは、$10^7$ オーダーで添字アクセス一杯使うプログラムはPyPyで出しましょう。（1TLE）
import sys
h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (h + 10001)
dp[0] = 0
for line in sys.stdin:
a, b = map(int, line.split())
for i in range(h):
if dp[i] == INF:
continue
dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))
高速化
NumPyを使えば、高速化できる。更新方法を、以下のように貰うDPに整理しなおす。
- $DP[k] = \min_{i}(DP[k-A_i]+B_i)$
一般に、配るDPは、参照箇所が1つで更新箇所がバラバラになる。一方貰うDPは、参照箇所が複数で更新箇所が1つになる。
NumPyは、更新箇所がバラバラ（しかも重複するかも知れない）だと簡潔な記述が難しいが、参照箇所がバラバラの場合はindexの配列で簡単に取得できる。
aaa = np.arange(10) * 10 # => [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] aaa[[1, 3, 3, 2, 5]] # => [10, 30, 30, 20, 50]
貰うDPに書き直して、「ダメージを $k$ 以上与えるのに必要な最小魔力」を $k$ の小さい方から埋めていく。
ここで $A_i,B_i$ についてベクトル化しておけば、1回の更新をNumPyに一括計算させることができ、理論上の計算量は変わらないものの速度は大幅に改善される。
aaa = 各魔法で与えられるダメージのNumPy配列
bbb = 各魔法で消費する魔力のNumPy配列
for k in range(1, h + 1):
dp[k] = (dp[k - aaa] + bbb).min()
$k-A_i$ が負になる場合に注意。強制的に0にするか、DP配列の末尾を長めに作って末尾からアクセスされた場合でもおかしくならないようにする。
高速化その2
分枝限定法を用いれば、無駄な探索が減り速くなる。 （ただ、問題から実装に落とし込むのは結構手間なので、普通のナップサックで通る場合はわざわざ使う必要は薄い。だが効果は大きい）
まず、大元の問題から何かを1つ固定して、部分問題へ分割していく探索の過程を木構造でイメージする。
今回は、魔法のコスパのよい方から、それぞれを何回使うかで分岐していく。
$f(k,i,c)=$ 「既に魔力を $c$ 使った状態で、コスパ順位 $i$ 番目以降の魔法だけを使って残り体力 $k$ を削るとき、必要な全体の魔力の最小値」とする。 問題全体は $f(H,0,0)$ を求めればよい。
f(H,0,0)
i=0を何回使うか ↙0 ↓1 ↘2 ....
f(H, 1, 0) f(H-A0, 1, B0) f(H-A0*2, 1, B0*2)
i=1を何回使うか ↓0↓1↓2... ↓0↓1↓2... ↓0↓1↓2...
...
ここで、$f(k,i,c)$ が取り得る下限を考える。これには「緩和問題」といって、元の問題より答えを求めやすく、かつ元の問題より悪くなることはないような指標を用いる。
ナップサック問題では「各魔法は0.3回とか、小数回数使ってもよい」とした問題を緩和問題とするのが一般的。 すると、残っている中でコスパ最良のもの、つまり $i$ 番目の魔法を使えるだけ使うのが最も魔力を抑える方法となり、単純な割り算で計算できる。
緩和問題の解 $f'(k,i,c)=k/A_i*B_i+c$ となり、これがその部分問題を探索して得られる下限となる。
i=5 Ai=3 Bi=7 c=10 f'(14, 5, 10) = 14/3 * 7 + 10 = 42.666... → f(14, 5, 10)以下の解が 42.666... より小さくなることはない
さて、木構造のどのルートでもいいので一番下まで探索して、とりあえず1つの実現可能な値（緩和問題でなく元の問題の、最良とは限らない解）が求まったとする。 これを暫定最良値とする。
すると、ある部分問題 $f(k,i,c)$ を探索するとき $f'(k,i,c) \ge 暫定最良値$ なら 「これ以下を探索しても暫定最良値より良い解は見つからない」ことがわかるので、ばっさり切ってしまえる。
木構造の下の方は切っても恩恵は少ないが、わりと $i=2～3$ くらいの上位の部分問題も普通に切れる。 よりよい最良値が見つかったら更新すれば、探索範囲がどんどん限定され、高速になる。
（なんか名指しっぽくなっちゃうのもアレだけど、一応Python内最速コードなので、注意喚起として）
Python3の提出で、50～70ms台などでACしている中に、似たようにコスパのよい方から試して単に「DP配列を更新できなくなったら」打ちきりという解法があったが、嘘解法と思われる。
1 3 1 1 3 2 4 3
上のサンプルは当然、体力1さえ減らせばいいので(1,1)の魔法を使えば魔力も1で済む。 しかしその解法では2が出力される。
これはコスパのよい順に魔法をソートすると(3,2)→(4,3)→(1,1)となり、H=1を削るのに必要な魔力をDPで更新すると
- (3,2)を使うと2
- (4,3)を使うと3→打ち切られてしまう
- (1,1)は探索されない
F - Silver Fox vs Monster
問題
- モンスターが $N$ 体、数直線上に並んでおり、$i$ 番目のモンスターの位置は $X_i$、体力は $H_i$
- 爆弾を使って攻撃し、全てのモンスターの体力を0以下にする
- 爆弾を座標 $X$ で使うと、$X-D$ 以上 $X+D$ 以下にいるモンスターの体力を等しく $A$ ずつ減らす
- 攻撃する必要回数の最小値を求めよ
- $1 \le N \le 2 \times 10^5$
- $0 \le D,X_i \le 10^9$
- $1 \le A,H_i \le 10^9$
解法
ソートして貪欲。優先度付きキューを用いる。
左端のモンスター $i$ を考える。
$X_i$ を範囲に含むように $H_i/A$ 回（切り上げ）攻撃しなきゃいけない。 どこに爆弾を置けばよいかというと、左にはモンスターがいなくて爆風が届いても無駄なので、モンスター $i$ が爆風のぎりぎり左に入るように置けばよい（つまり $X_i+D$）。
🧿 💣 |---D----|----D---|
すると、$X_i+2D$ までは、その爆弾により攻撃できる。
モンスターを左から順に処理していけば、常に処理中のモンスターが残っている中での左端のモンスターになる。 「現時点で、処理済みモンスターを倒すために使用した爆風で、ついでに与えられるダメージ」を更新していけばよい。
A=1
H 5 7 6 6
🧿 🧿 💣 🧿 🧿
|--------2D--------| 5回分の攻撃
|--------2D--------| 2回分の攻撃
-----------------------------
↑5回分のダメージは与えられているので、残り2回分だけ与えればよい
↑計7回分の攻撃で、勝手に倒せている
↑5回分の爆風は届かないので、新たに4回分の攻撃が必要
これは、モンスターを $X_i$ の小さい方から取り出すリストに、爆弾を置く毎に「爆風が切れる座標」も追加していけばよい。 それには、優先度付きキューを利用する。
$atk$ を「現在有効な、ついでに与えられる攻撃回数」として、優先度キューから $X_i,X_b$ が小さい方から順に取り出す。
- $(X_i, 0, H_i)$: モンスターを表す
- $atk$ 以内で倒せる→何もしなくてよし
- $atk$ 以内で倒せない→追加で必要な爆弾数 $exatk$ を求める。$atk$ に $exatk$ を足し、$(X_i+2D,1,exatk)$ をキューに追加する
- $(X_b, 1, exatk)$: 爆風が切れることを表す
- $atk$ から $exatk$ を引く
順番の注意点として、$X_b$ と $X_i$ が重なった場合は爆風はギリギリ有効なので、モンスターの方を先に処理する必要がある。 よって、識別コード0,1は、モンスターの方に小さい0を割り当てる。
計算量は、最初の優先度付きキューの構築に $O(N)$、 左端から処理する（モンスター or 爆風）が最大 $2N$、1回の処理に $O(\log{N})$ 必要なので、あわせて $O(N \log{N})$ で間に合う。
import sys
from heapq import heapify, heappop, heappush
n, d, a = list(map(int, input().split()))
xh = []
for line in sys.stdin:
x, h = map(int, line.split())
xh.append((x, 0, h))
heapify(xh)
atk_cnt = 0
ans = 0
while xh:
x, t, h = heappop(xh)
if t == 0:
if atk_cnt * a >= h:
continue
remain = h - atk_cnt * a
new_atk = (remain - 1) // a + 1
heappush(xh, (x + 2 * d, 1, new_atk))
ans += new_atk
atk_cnt += new_atk
else:
atk_cnt -= h
print(ans)
もしくは優先度キューを使わなくても、$X_b$ となりうる位置は $X_i$ からあらかじめわかるので、最初に全てまとめてソートしてもよい。
「モンスター $i$ が左端で残っていた場合の $exatk$」を $i$ ごとに記録しておけば、$X_b$ が取り出されたときに遡って $atk$ からいくら引けばよいのかわかる。
