概要

この問題は、1次元に並んだ住民の間で広がる感染シミュレーションにおいて、最終的に感染する住民の人数を求める問題です。 各住民の免疫力 \(H_i\) と、隣接する感染者から受けるダメージ \(D\) が与えられます。

愚直に1ラウンドずつシミュレーションを行うと、最大で \(10^9\) 以上のラウンド数がかかるため実行時間制限に間に合いません。そこで、ダイクストラ法（最短経路アルゴリズム）を応用して、各住民が「最短で何ラウンド目に感染するか」を高速に求めることで解決します。

---

考察

1. 愚直なシミュレーションが間に合わない理由

住民の初期免疫力 \(H_i\) は最大で \(10^9\)、毎ラウンド減少する値 \(D\) は最小で \(1\) です。 例えば、住民が横一列に並んでおり、端から順番に \(D=1\) で感染が伝わっていく場合、最悪で \(10^9\) ラウンド以上の計算が必要になります。 したがって、1ラウンドずつ状態を更新する素朴なシミュレーション（時間計算量 \(O(N \times \text{ラウンド数})\)）では TLE（実行時間制限超過） になります。

2. ダイクストラ法への帰着

感染の拡大は、すでに感染した隣の住民から「ダメージ」が伝播するプロセスです。 これは、グラフにおける最短経路問題に非常によく似ています。 各住民 \(i\) について、「最短で何ラウンド目に感染するか」を dist[i] と定義します。

初期状態で \(H_i \leq 0\) の住民はラウンド \(0\) で感染します（dist[i] = 0）。 これらをスタート地点として、ダイクストラ法のように「感染ラウンドが早い住民」から順番に確定させていき、隣接する未感染の住民の感染ラウンドを更新していきます。

3. 隣接する住民からの感染ラウンドの計算

住民 \(v\) の隣接住民のうち、既に感染している住民の感染ラウンドを \(p_1, p_2\) （\(p_1 \leq p_2\)）とします。 住民 \(v\) が感染するラウンドは、以下の3つのケースの最小値になります。

ケースA: 隣接する感染者が0人の場合

当然、感染することはありません。感染ラウンドは無限大（\(\infty\)）です。

ケースB: 隣接する感染者が1人の場合（または片方からしか影響を受けない場合）

感染者から毎ラウンド \(D\) のダメージを受けます。 必要なラウンド数は \(\lceil H_v / D \rceil\) です。 したがって、感染ラウンドは \(p_1 + \lceil H_v / D \rceil\) となります。

ケースC: 隣接する感染者が2人の場合

2人の感染時期の差 \(diff = p_2 - p_1\) によって状況が変わります。

• \(diff \geq \lceil H_v / D \rceil\) のとき 2人目が感染する前に、1人目からのダメージだけで \(v\) が感染してしまいます。そのため、実質的にケースBと同じになります。
• \(diff < \lceil H_v / D \rceil\) のとき 最初の \(diff\) ラウンドの間は、1人目からのみダメージ（計 \(diff \times D\)）を受けます。 その後（ラウンド \(p_2\) 以降）は、両方の隣人から毎ラウンド \(2D\) のダメージを受けます。 ラウンド \(p_2\) の時点での残り免疫力は \(rem\_H = H_v - diff \times D\) です。 ここから毎ラウンド \(2D\) ずつ減少するため、追加で必要なラウンド数は \(\lceil rem\_H / (2D) \rceil\) となります。 したがって、感染ラウンドは \(p_2 + \lceil rem\_H / (2D) \rceil\) となります。

4. 伝播の終了条件の処理

問題文には「このラウンドで新たに感染状態になった住民が 1 人もいなかった場合、伝播はただちに終了する」という重要なルールがあります。

ダイクストラ法で求めた dist[i] は、伝播が無限に続くとした場合の感染ラウンドです。 しかし、途中のラウンド \(r\) で「新規感染者が \(0\) 人」になると、それ以降のラウンドは行われません。つまり、ラウンド \(r\) 以降に感染するはずだった住民は、実際には感染しないまま終了します。

これを判定するために、到達可能なラウンドの集合をソートして重複を排除したリスト times を作成します。 実際の感染が途切れずに続くためには、ラウンドが \(0, 1, 2, \dots, k\) と連続して存在する必要があります。 例えば、times = [0, 1, 3] のように \(2\) が抜けている場合、ラウンド \(2\) で新規感染者が \(0\) 人だったことを意味するため、ラウンド \(3\) 以降の感染は発生しません。 したがって、times[i] == i を満たす最大の \(i\) を \(k\) としたとき、dist[i] <= k である住民のみが最終的に感染します。

---

アルゴリズム

1. 初期化:
   • dist 配列を無限大（INF）で初期化。
   • 初期状態で \(H_i \leq 0\) である住民 \(i\) について、dist[i] = 0 とし、優先度付きキュー pq に追加。
2. ダイクストラ法による最短ラウンドの探索:
   • pq から最も感染ラウンドが早い住民 \(u\) を取り出す。
   • 隣接する住民 \(v \in \{u-1, u+1\}\) に対して、すでに確定した隣人の感染ラウンド（parent_vals[v]）を追加し、関数 calc_next(v) を用いて \(v\) の新たな感染ラウンドを計算。
   • 計算された値が現在の dist[v] より小さければ更新し、pq に追加。
3. 終了条件の判定:
   • 求められた dist のうち、INF でない値を集めてソート・重複排除し、連続する最大のラウンド \(k\) を求める。
4. 集計:
   • dist[i] <= k である住民の数をカウントして出力。

---

計算量

• 時間計算量: \(O(N \log N)\)
  • 住民の数 \(N\) に対し、グラフの頂点数は \(N\)、辺数は最大 \(2N\) です。
  • ダイクストラ法における優先度付きキューの操作回数は \(O(N)\) 回であり、1回あたりの操作は \(O(\log N)\) です。
  • calc_next の計算は \(O(1)\) で行えます。
  • 最後のソートおよび重複排除も \(O(N \log N)\) で実行可能です。
• 空間計算量: \(O(N)\)
  • dist, visited, parent_vals などの配列を保持するために \(O(N)\) のメモリを使用します。

---

実装のポイント

• 切り上げ除算の工夫:

  • \(\lceil A / B \rceil\) を整数演算で求める際、(A + B - 1) / B というテクニックを使用しています。これにより、浮動小数点数の精度問題を回避できます。

• オーバーフローへの注意:

  • \(H_i\) や \(D\) は最大 \(10^9\) であり、計算の過程で非常に大きな値になります。C++では long long 型を使用し、無限大を表す定数 INF も十分大きな値（コード中では 4e18）に設定する必要があります。

    ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 4e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;

    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }

    vector<long long> dist(N, INF);
    vector<bool> visited(N, false);
    vector<vector<long long>> parent_vals(N);

    using PLI = pair<long long, int>;
    priority_queue<PLI, vector<PLI>, greater<PLI>> pq;

    for (int i = 0; i < N; ++i) {
        if (H[i] <= 0) {
            dist[i] = 0;
            pq.push({0, i});
        }
    }

    auto calc_next = [&](int v) -> long long {
        if (H[v] <= 0) return 0;
        const auto& p = parent_vals[v];
        if (p.empty()) return INF;
        long long steps1 = (H[v] + D - 1) / D;
        if (p.size() == 1) {
            return p[0] + steps1;
        }
        long long p1 = p[0];
        long long p2 = p[1];
        long long d1 = p1 + steps1;
        long long d2 = p2 + steps1;

        long long p_max = max(p1, p2);
        long long p_min = min(p1, p2);
        long long diff = p_max - p_min;

        long long d3;
        if (diff >= steps1) {
            d3 = p_min + steps1;
        } else {
            long long rem_H = H[v] - diff * D;
            long long steps3 = (rem_H + 2 * D - 1) / (2 * D);
            d3 = p_max + steps3;
        }
        return min({d1, d2, d3});
    };

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (int v : {u - 1, u + 1}) {
            if (v < 0 || v >= N) continue;
            if (visited[v]) continue;

            parent_vals[v].push_back(d);
            long long new_d = calc_next(v);
            if (new_d < dist[v]) {
                dist[v] = new_d;
                pq.push({dist[v], v});
            }
        }
    }

    vector<long long> times;
    for (int i = 0; i < N; ++i) {
        if (dist[i] != INF) {
            times.push_back(dist[i]);
        }
    }

    if (times.empty()) {
        cout << 0 << "\n";
        return 0;
    }

    sort(times.begin(), times.end());
    times.erase(unique(times.begin(), times.end()), times.end());

    long long k = 0;
    for (size_t i = 0; i < times.size(); ++i) {
        if (times[i] == (long long)i) {
            k = i;
        } else {
            break;
        }
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (dist[i] <= k) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。