E - 感染シミュレーション / Infection Simulation 解説 by admin
gpt-5.5-high概要
感染者が隣人へ毎ラウンド \(D\) ずつダメージを与えるとき、伝播が止まるまでに感染する人数を求めます。
免疫力を「あと何回攻撃を受けると感染するか」に変換し、感染が起こる時刻を優先度付きキューで小さい順に処理します。
考察
住民 \(i\) の免疫力が \(H_i > 0\) のとき、この住民が感染するために必要な攻撃回数は
\[ K_i = \left\lceil \frac{H_i}{D} \right\rceil \]
です。
例えば \(H_i = 10, D = 3\) なら、\(3\) 回では \(9\) しか減らせないので、\(4\) 回攻撃を受ける必要があります。
素朴にラウンドごとにシミュレーションすると、\(H_i\) や \(D\) の値によっては感染までに \(10^9\) ラウンドかかることがあります。
\(N\) は \(2 \times 10^5\) ですが、ラウンド数が非常に大きくなり得るため、単純なシミュレーションは間に合いません。
そこで、「次に誰が何ラウンド目に感染するか」というイベントだけを処理します。
住民 \(i\) の左右の隣人が感染した時刻が分かっていると、住民 \(i\) が感染する最短時刻を計算できます。
感染時刻を「そのラウンドの終了時に感染する時刻」とします。初期感染者の感染時刻は \(0\) です。
片方の隣人だけが感染している場合
隣人が時刻 \(a\) に感染したとします。
その隣人はラウンド \(a+1\) から攻撃を始めます。
住民 \(i\) が感染するには \(K_i\) 回攻撃を受ければよいので、感染時刻は
\[ a + K_i \]
です。
両方の隣人が感染している場合
左隣と右隣の感染時刻を \(a, b\) とし、\(a \leq b\) とします。
時刻 \(b\) までは、先に感染した隣人だけが攻撃します。
その間に受ける攻撃回数は
\[ b - a \]
回です。
もし
\[ K_i \leq b - a \]
なら、片方からの攻撃だけで感染するので、感染時刻は
\[ a + K_i \]
です。
そうでない場合、時刻 \(b\) 以降は両隣から毎ラウンド合計 \(2\) 回攻撃を受けます。
時刻 \(t\) までに受ける攻撃回数は
\[ (b-a) + 2(t-b) \]
なので、これが \(K_i\) 以上になる最小の \(t\) は
\[ t = \left\lceil \frac{K_i + a + b}{2} \right\rceil \]
です。
また、この問題では「あるラウンドで新たな感染者が 1 人も出なかったら、そこで終了する」という条件が重要です。
つまり、たとえ理論上はラウンド \(10\) で感染する人がいても、ラウンド \(3\) で新規感染者がいなければ、そこで終了してしまい、ラウンド \(10\) には到達しません。
そのため、感染イベントを時刻順に処理しながら、
- ラウンド \(1\) に感染者がいるか
- ラウンド \(2\) に感染者がいるか
- ラウンド \(3\) に感染者がいるか
を順番に確認します。
次に起こる感染時刻が、現在必要なラウンドより後なら、そこで伝播終了です。
アルゴリズム
各住民について、以下を管理します。
infected[i]: すでに感染しているかleft_time[i]: 左隣が感染した時刻right_time[i]: 右隣が感染した時刻cand[i]: 現時点で分かっている住民 \(i\) の最短感染時刻
感染候補は優先度付きキューで管理し、感染時刻が小さいものから取り出します。
手順は以下です。
- 各住民について、\(H_i \leq 0\) なら初期感染者とする。
- \(H_i > 0\) の住民について、必要攻撃回数
$\( K_i = \left\lceil \frac{H_i}{D} \right\rceil \)$
を計算する。
3. 初期感染者の隣人について、感染した隣人の時刻を \(0\) として記録し、感染候補時刻を計算して優先度付きキューに入れる。
4. expected = 1 とする。これは「次に新規感染者が出なければならないラウンド」を表す。
5. 優先度付きキューから最小の感染時刻 \(t\) を取り出す。
- キューが空なら終了。
- \(t > expected\) なら、ラウンド expected で新規感染者がいないため終了。
6. 時刻 \(t\) に感染する住民をすべてまとめて感染済みにする。
7. 新たに感染した住民の隣人について、感染候補時刻を再計算し、必要なら優先度付きキューに追加する。
8. \(t = expected\) なら、次のラウンドを見るために expected を \(1\) 増やす。
9. 5 に戻る。
同じ時刻に複数人が感染する可能性があるため、同じ感染時刻 \(t\) の候補はまとめて処理します。
これは、「ラウンド終了時に同時に感染する」という問題文の条件に対応しています。
計算量
- 時間計算量: \(O(N \log N)\)
- 空間計算量: \(O(N)\)
各住民は高々一度感染し、隣人の候補更新も定数回程度です。優先度付きキューへの追加・取り出しに \(O(\log N)\) かかるため、全体で \(O(N \log N)\) です。
実装のポイント
優先度付きキューには、古い候補が残ることがあります。
例えば、片方の隣人だけが感染しているときに計算した候補時刻よりも、あとからもう片方の隣人も感染したことで、より早い候補時刻が分かる場合があります。
そのため、キューから取り出したときに
if (infected[i] || cand[i] != t)
のように確認し、すでに感染済みだったり、古い候補だったりするものは捨てます。
また、感染時刻の計算では \(H_i, D\) が最大 \(10^9\) であり、時刻も大きくなり得るため、long long を使う必要があります。
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
ll D;
cin >> N >> D;
vector<ll> H(N), K(N, 0);
for (int i = 0; i < N; i++) {
cin >> H[i];
if (H[i] > 0) K[i] = (H[i] + D - 1) / D;
}
const ll INF = (1LL << 62);
vector<char> infected(N, false);
vector<ll> left_time(N, INF), right_time(N, INF), cand(N, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
auto calc = [&](int i) -> ll {
if (infected[i]) return INF;
ll k = K[i];
bool hasL = (left_time[i] != INF);
bool hasR = (right_time[i] != INF);
if (!hasL && !hasR) return INF;
if (hasL && !hasR) return left_time[i] + k;
if (!hasL && hasR) return right_time[i] + k;
ll a = left_time[i], b = right_time[i];
if (a > b) swap(a, b);
if (a + k <= b) return a + k;
return (k + a + b + 1) / 2;
};
auto relax = [&](int i) {
if (i < 0 || i >= N || infected[i]) return;
ll c = calc(i);
if (c < cand[i]) {
cand[i] = c;
pq.emplace(c, i);
}
};
ll ans = 0;
for (int i = 0; i < N; i++) {
if (H[i] <= 0) {
infected[i] = true;
ans++;
}
}
for (int i = 0; i < N; i++) {
if (!infected[i]) continue;
if (i > 0 && !infected[i - 1]) {
right_time[i - 1] = 0;
relax(i - 1);
}
if (i + 1 < N && !infected[i + 1]) {
left_time[i + 1] = 0;
relax(i + 1);
}
}
auto clean = [&]() {
while (!pq.empty()) {
auto [t, i] = pq.top();
if (infected[i] || cand[i] != t) pq.pop();
else break;
}
};
ll expected = 1;
while (true) {
clean();
if (pq.empty()) break;
ll t = pq.top().first;
if (t > expected) break;
vector<int> group;
while (true) {
clean();
if (pq.empty() || pq.top().first != t) break;
auto [tt, i] = pq.top();
pq.pop();
if (!infected[i] && cand[i] == tt) {
group.push_back(i);
}
}
if (group.empty()) continue;
for (int i : group) {
if (!infected[i]) {
infected[i] = true;
ans++;
}
}
for (int i : group) {
if (i > 0 && !infected[i - 1]) {
if (right_time[i - 1] > t) {
right_time[i - 1] = t;
relax(i - 1);
}
}
if (i + 1 < N && !infected[i + 1]) {
if (left_time[i + 1] > t) {
left_time[i + 1] = t;
relax(i + 1);
}
}
}
if (t == expected) expected++;
}
cout << ans << '\n';
return 0;
}
この解説は gpt-5.5-high によって生成されました。
投稿日時:
最終更新: