E - 感染シミュレーション / Infection Simulation Editorial by admin
gemini-3.5-flash-highOverview
This problem asks us to simulate how an infection spreads left and right among residents lined up in a row. By applying Dijkstra’s algorithm (shortest path problem) to efficiently find the “round (time)” when each resident becomes infected, and terminating the transmission at the “first round where no new infected person appears,” we can determine the final number of infected residents.
Analysis
1. Limits of Naive Simulation
If we perform a naive simulation where we update the immunity of all residents in every round, we would need to simulate \(O(N)\) rounds in the worst case, resulting in an overall time complexity of \(O(N^2)\). Since \(N \le 2 \times 10^5\), this approach will exceed the time limit (TLE). Therefore, we need to directly and quickly calculate the exact round in which each resident becomes infected.
2. Number of Rounds Required for Infection
If resident \(i\) receives damage from only one side in isolation, the amount of damage required to reach the infected state (immunity \(\le 0\)) is \(H_i\). Since they receive \(D\) damage per round from one infected neighbor, the number of rounds required is \(C_i = \max(0, \lceil H_i / D \rceil)\).
3. Influence from Adjacent Residents (Infection from Both Sides)
Let \(L\) and \(R\) be the rounds in which resident \(i\)’s left and right neighbors, \(i-1\) and \(i+1\), become infected (assume \(L \le R\) for convenience). The round \(d_i\) in which resident \(i\) becomes infected is the minimum of the following three scenarios:
- Infected by receiving damage only from the left side (\(i-1\)) \(d_i = L + C_i\)
- Infected by receiving damage only from the right side (\(i+1\)) \(d_i = R + C_i\)
- Infected by receiving damage from both sides Until time \(R\), they receive damage only from the left side (totaling \((R - L) \times D\)). From time \(R+1\) onwards, they receive damage from both sides (\(2D\) per round). In this case, the infection round is \(\lceil (L + R + C_i) / 2 \rceil\). However, since they start receiving damage from both sides at time \(R+1\) at the earliest, this value must be at least \(R+1\). Therefore, the infection round for this scenario can be expressed as \(\max( \lceil (L + R + C_i) / 2 \rceil, R + 1 )\).
Thus, the infection round \(d_i\) of each resident is determined by the infection rounds of their adjacent neighbors \(d_{i-1}\) and \(d_{i+1}\). This means we can model the spread of infection as a shortest path problem on a graph (Dijkstra’s algorithm).
4. Termination Condition for Transmission
The problem statement says, “If there are no residents who newly become infected in this round, the transmission immediately ends.” This means that, if we consider the set of infection rounds \(d_i\) calculated for all residents, if there exists a “smallest round \(r_{\text{stop}}\) where no one becomes infected,” any resident who would have been infected in or after that round (\(r_{\text{stop}}\) or later) will not actually become infected.
For example, if the calculated infection rounds of the residents are \(\{0, 1, 2, 4\}\), since \(0\) people newly become infected in round \(3\), the transmission ends at round \(3\), and the resident who was supposed to be infected in round \(4\) remains uninfected. Therefore, the final infected residents are only those who were infected in rounds \(\{0, 1, 2\}\).
Algorithm
- Preparation: For each resident \(i\), calculate the number of rounds required for infection: \(C_i = \max(0, \lceil H_i / D \rceil)\).
- Initialization: For residents who are already infected in the initial state (\(H_i \le 0\)), set their infection round to \(d_i = 0\). For all other residents, set \(d_i = \infty\). Push the residents with \(d_i = 0\) into a priority queue (heap).
- Determining Shortest Paths (Infection Rounds) via Dijkstra’s Algorithm:
Pop the resident \(u\) with the smallest infection round \(d_u\) from the queue, and attempt to update the infection round \(d_v\) of its neighbors \(v \in \{u-1, u+1\}\).
Let \(L = d_{v-1}\) and \(R = d_{v+1}\) be the infection rounds of the left and right neighbors of \(v\). The minimum of the three scenarios described above becomes the new candidate value
new_d. If \(d_v > \text{new\_d}\), update \(d_v\) tonew_dand push \(v\) into the queue. - Termination Check and Counting: After determining \(d_i\) for all residents, create a set of existing \(d_i\) values (excluding \(\infty\)). Search for \(t = 1, 2, \dots\) to find the smallest positive integer \(r_{\text{stop}}\) that is not in the set. Finally, count and output the number of residents who satisfy \(d_i < r_{\text{stop}}\).
Complexity
- Time Complexity: \(O(N \log N)\) For \(N\) residents, each resident’s state is updated at most twice (from their left and right neighbors), meaning the number of push/pop operations on the priority queue is at most \(O(N)\). Since each queue operation takes \(O(\log N)\) time, the overall time complexity is \(O(N \log N)\), which is well within the execution time limit.
- Space Complexity: \(O(N)\) The arrays storing information for each resident (such as \(H, C, d\)) and the size of the priority queue are at most \(O(N)\).
Implementation Details
Ceiling Division: To perform the calculation of \(\lceil A / B \rceil\) accurately using only integer types, it can be implemented as
(A + B - 1) // B.Using Sentinels: To prevent out-of-bounds array access (at index \(0\) or \(N+1\)), placing sentinels with an initial value of \(\infty\) at both ends of the array allows for cleaner boundary exception handling.
Search Range for the Termination Round: Since there are \(N\) residents in total, the round \(r_{\text{stop}}\) where no one becomes infected is at most \(N+1\). Therefore, searching from \(1\) to \(N+1\) is sufficient.
Source Code
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()
This editorial was generated by gemini-3.5-flash-high.
posted:
last update: