E - 感染シミュレーション / Infection Simulation 解説 by admin
gemini-3.5-flash-high概要
一列に並んだ住民の間で、感染が左右に広がっていく様子をシミュレーションする問題です。 各住民が感染する「ラウンド（時刻）」をダイクストラ法（最短経路問題）を応用して効率的に求め、「新たに感染者が現れなかった最初のラウンド」で伝播を打ち切ることで、最終的な感染者数を求めます。
考察
1. 素朴なシミュレーションの限界
毎ラウンドごとに全員の免疫力を更新するような素朴なシミュレーションを行うと、最悪の場合 \(O(N)\) ラウンドのシミュレーションが必要になり、全体の計算量が \(O(N^2)\) となってしまいます。\(N \le 2 \times 10^5\) であるため、このアプローチでは実行時間制限（TLE）に間に合いません。 そのため、各住民が何ラウンド目に感染するかを直接、高速に計算する必要があります。
2. 感染に必要なラウンド数
住民 \(i\) が単独で片側からのみダメージを受ける場合、感染状態（免疫力 \(\le 0\)）になるために必要なダメージ量は \(H_i\) です。 1つの感染した隣人から毎ラウンド \(D\) のダメージを受けるため、必要なラウンド数は \(C_i = \max(0, \lceil H_i / D \rceil)\) となります。
3. 隣接する住民からの影響（両側からの感染）
住民 \(i\) の左右の隣人 \(i-1, i+1\) がそれぞれラウンド \(L, R\) で感染するとします（便宜上 \(L \le R\) とします）。 住民 \(i\) が感染するラウンド \(d_i\) は、以下の3つのパターンの最小値になります。
- 左側（\(i-1\)）からのみダメージを受けて感染する場合 \(d_i = L + C_i\)
- 右側（\(i+1\)）からのみダメージを受けて感染する場合 \(d_i = R + C_i\)
- 両側からダメージを受けて感染する場合 時刻 \(R\) までは左側からのみダメージを受け（計 \((R - L) \times D\)）、時刻 \(R+1\) 以降は両側からダメージ（毎ラウンド \(2D\)）を受けます。 このとき、感染するラウンドは \(\lceil (L + R + C_i) / 2 \rceil\) となります。ただし、両側からダメージを受け始めるのは早くても時刻 \(R+1\) 以降なので、値は最低でも \(R+1\) になります。 したがって、このパターンの感染ラウンドは \(\max( \lceil (L + R + C_i) / 2 \rceil, R + 1 )\) と表せます。
このように、各住民の感染ラウンド \(d_i\) は、隣接する住民の感染ラウンド \(d_{i-1}, d_{i+1}\) から決定されます。これは、感染の広がりをグラフの最短経路問題（ダイクストラ法）として捉えられることを意味します。
4. 伝播の終了条件
問題文には「このラウンドで新たに感染状態になった住民が 1 人もいなかった場合、伝播はただちに終了する」とあります。 これは、すべての住民について求めた感染ラウンド \(d_i\) の集合を考えたとき、「誰も感染しなかった最小のラウンド \(r_{\text{stop}}\)」が存在すれば、それ以降（\(r_{\text{stop}}\) 以降）に感染するはずだった住民は実際には感染しないということを意味します。
例えば、各住民の感染ラウンドが \(\{0, 1, 2, 4\}\) だった場合、ラウンド \(3\) で新たに感染した人が \(0\) 人であるため、伝播はラウンド \(3\) の時点で終了し、ラウンド \(4\) で感染するはずだった住民は感染しません。したがって、最終的な感染者は \(\{0, 1, 2\}\) ラウンドに感染した住民のみになります。
アルゴリズム
- 準備: 各住民 \(i\) について、感染に必要なラウンド数 \(C_i = \max(0, \lceil H_i / D \rceil)\) を計算します。
- 初期化: 初期状態で感染している住民（\(H_i \le 0\)）の感染ラウンドを \(d_i = 0\) とし、それ以外の住民は \(d_i = \infty\) とします。 \(d_i = 0\) の住民を優先度付きキュー（ヒープ）に追加します。
- ダイクストラ法による最短路（感染ラウンド）の決定:
キューから最も感染ラウンド \(d_u\) が小さい住民 \(u\) を取り出し、その隣人 \(v \in \{u-1, u+1\}\) の感染ラウンド \(d_v\) の更新を試みます。
隣人 \(v\) の左右の住民の感染ラウンドを \(L = d_{v-1}, R = d_{v+1}\) としたとき、前述の3つのパターンの最小値を新たな候補値
new_dとし、\(d_v > \text{new\_d}\) であれば \(d_v\) を更新してキューに追加します。 - 終了判定と集計: すべての住民の \(d_i\) が確定した後、存在する \(d_i\)（\(\infty\) を除く）の集合を作成します。 \(t = 1, 2, \dots\) の順に探索し、集合に含まれない最小の正の整数 \(r_{\text{stop}}\) を見つけます。 最終的に \(d_i < r_{\text{stop}}\) を満たす住民の数をカウントして出力します。
計算量
- 時間計算量: \(O(N \log N)\) 住民の数 \(N\) に対し、各住民は最大2回（左右の隣人から）更新されるため、優先度付きキューへの追加・取り出し操作は高々 \(O(N)\) 回です。キューの操作1回あたり \(O(\log N)\) かかるため、全体の時間計算量は \(O(N \log N)\) となり、実行時間制限に十分間に合います。
- 空間計算量: \(O(N)\) 各住民の情報を格納する配列（\(H, C, d\) など）および優先度付きキューのサイズは最大でも \(O(N)\) です。
実装のポイント
切り上げ除算の計算: \(\lceil A / B \rceil\) の計算は、整数型のみで正確に行うために
(A + B - 1) // Bと実装します。番兵の配置: 配列のインデックス範囲外（\(0\) 番目や \(N+1\) 番目）へのアクセスを防ぐため、両端に初期値 \(\infty\) の番兵を配置すると、境界値の例外処理をシンプルに書くことができます。
伝播終了ラウンドの探索範囲: 住民の総数は \(N\) 人なので、誰も感染しないラウンド \(r_{\text{stop}}\) は最大でも \(N+1\) になります。そのため、探索範囲は \(1\) から \(N+1\) まで調べれば十分です。
ソースコード
import sys
import heapq
def solve():
input = sys.stdin.read
data = input().split()
if not data:
return
N = int(data[0])
D = int(data[1])
H = [0] + [int(x) for x in data[2:N+2]]
C = [0] * (N + 2)
for i in range(1, N + 1):
hi = H[i]
if hi <= 0:
C[i] = 0
else:
C[i] = (hi + D - 1) // D
INF = 10**18
d = [INF] * (N + 2)
queue = []
for i in range(1, N + 1):
if H[i] <= 0:
d[i] = 0
queue.append((0, i))
heapq.heapify(queue)
heappush = heapq.heappush
heappop = heapq.heappop
while queue:
dist, u = heappop(queue)
if dist > d[u]:
continue
# v = u - 1
v = u - 1
if v >= 1:
if d[v] != 0:
L = d[v - 1]
R = d[v + 1]
Cv = C[v]
new_d = INF
if L != INF:
new_d = L + Cv
if R != INF:
val = R + Cv
if val < new_d:
new_d = val
if L != INF and R != INF:
max_LR = L if L > R else R
val = (L + R + Cv + 1) // 2
if max_LR + 1 > val:
val = max_LR + 1
if val < new_d:
new_d = val
if new_d < d[v]:
d[v] = new_d
heappush(queue, (new_d, v))
# v = u + 1
v = u + 1
if v <= N:
if d[v] != 0:
L = d[v - 1]
R = d[v + 1]
Cv = C[v]
new_d = INF
if L != INF:
new_d = L + Cv
if R != INF:
val = R + Cv
if val < new_d:
new_d = val
if L != INF and R != INF:
max_LR = L if L > R else R
val = (L + R + Cv + 1) // 2
if max_LR + 1 > val:
val = max_LR + 1
if val < new_d:
new_d = val
if new_d < d[v]:
d[v] = new_d
heappush(queue, (new_d, v))
active_ds = []
for i in range(1, N + 1):
if d[i] < INF:
active_ds.append(d[i])
if not active_ds:
print(0)
return
existing = set(active_ds)
r_stop = INF
for t in range(1, N + 2):
if t not in existing:
r_stop = t
break
ans = 0
for x in active_ds:
if x < r_stop:
ans += 1
print(ans)
if __name__ == '__main__':
solve()
この解説は gemini-3.5-flash-high によって生成されました。
投稿日時:
最終更新: