E - 感染シミュレーション / Infection Simulation 解説 by admin
gpt-5.5-high概要
免疫力が \(0\) 以下になった住民から感染が広がる過程をシミュレーションし、最終的に感染する人数を求めます。
各住民が感染する「最も早いラウンド」を優先度付きキューで管理し、ラウンドを 1 つずつ愚直に進めずに計算します。
考察
まず、免疫力 \(H_i > 0\) の住民 \(i\) が感染するために必要な攻撃回数を考えます。
感染している隣人 1 人から 1 ラウンド受けるダメージは \(D\) なので、住民 \(i\) が感染するには
\[ K_i = \left\lceil \frac{H_i}{D} \right\rceil \]
回分の攻撃を受ければ十分です。
例えば \(H_i = 25, D = 10\) なら、\(10\) ずつ減るので \(3\) 回攻撃を受けると感染します。
ここで「感染時刻」を次のように定義します。
- 最初から感染している住民の感染時刻は \(0\)
- ラウンド \(t\) の終了時に感染した住民の感染時刻は \(t\)
感染時刻が \(a\) の住民は、ラウンド \(a+1\) から隣人を攻撃します。
1 人の隣人から感染する場合
ある住民が、感染時刻 \(a\) の隣人 1 人からだけ攻撃される場合、\(K\) 回攻撃を受けるには \(K\) ラウンド必要なので、感染時刻は
\[ a + K \]
です。
2 人の隣人から感染する場合
左右の隣人がそれぞれ感染時刻 \(a, b\) で感染したとします。ただし \(a \leq b\) とします。
時刻 \(T\) までに受ける攻撃回数は
\[ (T-a) + \max(0, T-b) \]
です。
- 左の隣人はラウンド \(a+1\) から攻撃するので \(T-a\) 回
- 右の隣人はラウンド \(b+1\) から攻撃するので、\(T-b\) 回
となります。
もし 1 人目だけで 2 人目が感染する前に感染できるなら、
\[ a + K \leq b \]
なので、感染時刻は
\[ a + K \]
です。
そうでなければ、2 人から同時に攻撃を受ける期間が必要です。この場合、
\[ (T-a) + (T-b) \geq K \]
を満たす最小の \(T\) を求めればよいので、
\[ T = \left\lceil \frac{K+a+b}{2} \right\rceil \]
となります。
注意すべき点として、この問題では「あるラウンドで新たな感染者が 1 人も出なかったら、そこで終了」します。
つまり、仮にラウンドを続ければ後で感染する住民がいても、その前に空白のラウンドがあるなら実際には感染しません。
例えば、ある住民の感染予定時刻が \(2\) でも、ラウンド \(1\) で誰も感染しなかったなら、その住民は感染しません。
そのため、感染時刻を小さい順に見ていき、途中でラウンドが飛んだらそこで終了します。
アルゴリズム
優先度付きキューを使って、感染予定時刻が小さい住民から順に処理します。
管理する値
K[i]- 住民 \(i\) が感染するために必要な攻撃回数
- 最初から感染している住民は使わないので \(0\)
best[i]- 現時点で分かっている、住民 \(i\) の最も早い感染時刻
done[i]- 住民 \(i\) の感染が確定済みか
cnt[i]- 住民 \(i\) の感染済み隣人を何人見つけたか
first[i]- 最初に見つかった感染済み隣人の感染時刻
heap(感染予定時刻, 住民番号)を入れる優先度付きキュー
last- 現在までに、感染者が途切れずに発生している最後のラウンド
手順
- 最初から感染している住民、つまり \(H_i \leq 0\) の住民を感染時刻 \(0\) として優先度付きキューに入れる。
- それ以外の住民については \(K_i = \left\lceil \frac{H_i}{D} \right\rceil\) を計算しておく。
- 優先度付きキューから感染予定時刻が最小の住民を取り出す。
- すでに処理済み、または古い情報なら無視する。
- 感染予定時刻が
last + 1より大きいなら、感染者が出ないラウンドが存在するので終了する。 - その住民の感染を確定し、答えを \(1\) 増やす。
- その住民の左右の隣人について、感染予定時刻を更新する。
- 初めて感染済み隣人を見つけた場合は、時刻 \(t + K\)
- 2 人目の感染済み隣人を見つけた場合は、上で述べた式で計算する
- 更新された感染予定時刻を優先度付きキューに入れる。
ラウンドが途切れる判定
last は「ここまでの各ラウンドで少なくとも 1 人感染している」ことを表します。
初期状態では last = 0 です。
次に取り出した感染時刻が \(t\) のとき、
- \(t = last + 1\) なら、次のラウンドで感染者が出るので継続
- \(t \leq last\) なら、同じラウンドに複数人感染するだけなので継続
- \(t > last + 1\) なら、途中に感染者が出ないラウンドがあるので終了
です。
計算量
- 時間計算量: \(O(N \log N)\)
- 空間計算量: \(O(N)\)
各住民は高々 1 回感染が確定し、左右の隣人を調べるだけです。
優先度付きキューへの追加・取り出しに \(O(\log N)\) かかるため、全体で \(O(N \log N)\) です。
実装のポイント
感染時刻の計算では、割り算の切り上げに注意します。
\[ K_i = \left\lceil \frac{H_i}{D} \right\rceil \]
は Python では
K[i] = (H[i] + D - 1) // D
で計算できます。
また、
\[ \left\lceil \frac{K+a+b}{2} \right\rceil \]
は
(K + a + b + 1) // 2
で計算できます。
優先度付きキューには古い感染予定時刻が残ることがあるため、取り出したときに
if done[u] or t != best[u]:
continue
として無効な情報を捨てる必要があります。
ソースコード
import sys
import heapq
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
N, D = data[0], data[1]
INF = 10**30
K = [0] * N
best = [INF] * N
done = [False] * N
cnt = [0] * N
first = [0] * N
heap = []
for i in range(N):
h = data[2 + i]
if h <= 0:
best[i] = 0
heap.append((0, i))
else:
K[i] = (h + D - 1) // D
del data
heapq.heapify(heap)
heappush = heapq.heappush
heappop = heapq.heappop
ans = 0
last = 0
while heap:
t, u = heappop(heap)
if done[u] or t != best[u]:
continue
if t > 0 and t > last + 1:
break
done[u] = True
ans += 1
if t > 0 and t == last + 1:
last = t
if u > 0:
v = u - 1
if not done[v] and K[v]:
k = K[v]
c = cnt[v]
if c == 0:
cnt[v] = 1
first[v] = t
cand = t + k
else:
cnt[v] = 2
a = first[v]
if a + k <= t:
cand = a + k
else:
cand = (k + a + t + 1) // 2
if cand < best[v]:
best[v] = cand
heappush(heap, (cand, v))
if u + 1 < N:
v = u + 1
if not done[v] and K[v]:
k = K[v]
c = cnt[v]
if c == 0:
cnt[v] = 1
first[v] = t
cand = t + k
else:
cnt[v] = 2
a = first[v]
if a + k <= t:
cand = a + k
else:
cand = (k + a + t + 1) // 2
if cand < best[v]:
best[v] = cand
heappush(heap, (cand, v))
print(ans)
if __name__ == "__main__":
main()
この解説は gpt-5.5-high によって生成されました。
投稿日時:
最終更新: