概要

\(N\) 日周期で繰り返される経営計画において、指定された開始日 \(L\) と初期資金 \(S\) からスタートしたとき、いつ初めて資金が負になるか（倒産するか）を判定する問題です。資金の減少が続く場合は、非常に長い期間を経て倒産する可能性があるため、シミュレーションではなく数学的な計算とデータ構造を用いて高速に解く必要があります。

考察

1. 資金の変化を数式で表す

\(i\) 日目の資金の増減を \(D_i = A_i - B_i - C_i\) とします。 経営開始から \(k\) 日目の終了時点での資金は、以下のように表せます。 $\(\text{資金} = S + \sum_{d=1}^{k} D_{\text{（開始から } d \text{ 日目の計画上の日付）}}\)$

この和の部分を高速に計算するために、累積和を利用します。周期性を扱うため、計画 \(2\) サイクル分（\(2N\) 日分）の累積和 \(P_i\) を用意しておくと、どの開始日 \(L\) からの \(N\) 日間の変化も \(P_{L+r-1} - P_{L-2}\) のような形で表現できます。

2. 倒産するかどうかの判定

1サイクル（\(N\) 日間）の合計収支を \(T = \sum_{i=1}^N D_i\) とします。

• \(T \geq 0\) の場合: 最初の \(N\) 日間（1サイクル目）を乗り切れば、その後は資金が減らないか増えていくため、二度と倒産しません。
• \(T < 0\) の場合: 1サイクルごとに資金が \(|T|\) ずつ減っていくため、いつかは必ず倒産します。

3. 倒産するタイミングの特定

倒産が「何サイクル目」の「何日目」に起こるかを切り分けて考えます。

1. 最初の \(N\) 日間で倒産する場合: 最初のサイクル内での最小資金（相対値）を \(M\) としたとき、\(S + M < 0\) ならばこのサイクル中に倒産します。
2. それ以降のサイクルで倒産する場合: \(T < 0\) かつ最初のサイクルを乗り切った場合、何サイクルか経過した後に倒産します。 \(q\) サイクル経過後の資金の推移は、最初のサイクルの推移を \(q \times T\) だけ平行移動させたものになります。 「\(q\) サイクル目までは耐えられるが、\(q+1\) サイクル目で倒産する」という \(q\) は、不等式 \(S + qT + M < 0\) を解くことで \(q = \lfloor (S+M)/|T| \rfloor + 1\) のように求められます。

具体的な「日」を特定するには、累積和の配列に対して「ある値より小さくなる最初のインデックス」を探す必要があります。これはセグメント木を用いることで、1クエリあたり \(O(\log N)\) で実行可能です。

アルゴリズム

1. 前処理:
   • 各日の収支 \(D_i\) を計算し、2サイクル分（長さ \(2N\)）の累積和 \(P\) を作成する。
   • \(P\) をもとに、「区間の最小値」および「区間内で値が \(V\) 未満となる最初の位置」を取得できるセグメント木を構築する。
2. クエリ処理:
   • 開始日 \(L\) から \(N\) 日間での最小相対変化 \(M\) をセグメント木で求める。
   • \(S + M \geq 0\) かつ \(T \geq 0\) ならば、倒産しないため 0 を出力。
   • そうでない場合、倒産するサイクル \(q\) を計算する（\(S + M < 0\) なら \(q=0\)）。
   • \(q\) サイクル後の資金状況において、初めて資金が負になる日をセグメント木の find_first（二分探索）を用いて特定する。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • セグメント木の構築に \(O(N)\)。
  • 各クエリに対し、最小値取得と二分探索を \(O(\log N)\) で行うため、全体で \(O(Q \log N)\)。
• 空間計算量: \(O(N)\)
  • 累積和配列とセグメント木に \(O(N)\) のメモリを使用します。

実装のポイント

• 周期の扱い: 配列を \(2N\) で持つことで、開始日 \(L\) がどこであっても \(L\) 日目から \(L+N-1\) 日目までの連続した区間として扱えるようになり、実装が単純になります。

• セグメント木上の二分探索: 「値が \(V\) 未満となる最初の要素」を探す際、単純な二分探索をセグメント木の外で行うと \(O(\log^2 N)\) になりますが、セグメント木のノードを辿る形で行えば \(O(\log N)\) で済みます。

• オーバーフロー: 累積和や初期資金 \(S\) は最大で \(10^{12}\) 以上、計算過程ではそれ以上の値になる可能性があるため、long long 型（64bit整数）を使用する必要があります。

  ソースコード

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

using namespace std;

/**
 * Segment Tree to find the minimum value in a range and the first index satisfying a condition.
 * This will help in determining the first day the funds drop below zero.
 */
struct SegmentTree {
    int n;
    vector<long long> tree;
    static constexpr long long INF = 2e18; // Larger than any possible prefix sum

    SegmentTree(const vector<long long>& data) {
        n = (int)data.size();
        tree.resize(4 * n);
        build(data, 1, 0, n - 1);
    }

    // Build the segment tree with minimum values in each range.
    void build(const vector<long long>& data, int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(data, 2 * node, start, mid);
        build(data, 2 * node + 1, mid + 1, end);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }

    // Range minimum query to find the lowest fund level in a cycle.
    long long query_min(int node, int start, int end, int L, int R) {
        if (R < start || end < L) return INF;
        if (L <= start && end <= R) return tree[node];
        int mid = start + (end - start) / 2;
        return min(query_min(2 * node, start, mid, L, R),
                   query_min(2 * node + 1, mid + 1, end, L, R));
    }

    /**
     * Find the first index in [L, R] such that data[index] < V.
     * This is used to find the specific day of bankruptcy.
     */
    int find_first(int node, int start, int end, int L, int R, long long V) {
        // If the range is invalid or the minimum in this range is not less than V, return -1.
        if (R < start || end < L || tree[node] >= V) return -1;
        if (start == end) return start;
        int mid = start + (end - start) / 2;
        int res = find_first(2 * node, start, mid, L, R, V);
        if (res == -1) {
            res = find_first(2 * node + 1, mid + 1, end, L, R, V);
        }
        return res;
    }
};

int main() {
    // Fast I/O for competitive programming performance.
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // Daily net change in funds: D_i = A_i - B_i - C_i
    vector<long long> D(N);
    for (int i = 0; i < N; ++i) {
        long long A, B, C;
        cin >> A >> B >> C;
        D[i] = A - B - C;
    }

    // Prefix sums for two cycles (2N days) to handle the wrap-around logic easily.
    // P_data[i] stores the sum of D from day 1 to day i+1.
    vector<long long> P_data(2 * N);
    long long current_P = 0;
    for (int i = 0; i < 2 * N; ++i) {
        current_P += D[i % N];
        P_data[i] = current_P;
    }

    // Total fund change over one full cycle of N days.
    long long T = P_data[N - 1];

    // Build the segment tree on the prefix sums of the extended sequence.
    SegmentTree st(P_data);

    for (int j = 0; j < Q; ++j) {
        int L;
        long long S;
        cin >> L >> S;

        // P_prev is the prefix sum before starting on day L.
        long long P_prev = (L == 1) ? 0 : P_data[L - 2];
        
        // M is the minimum relative change in funds within the first N days starting from L.
        // The funds after r days starting from L are S + P_{L+r-1} - P_{L-1}.
        long long M = st.query_min(1, 0, 2 * N - 1, L - 1, L + N - 2) - P_prev;

        if (S + M >= 0) {
            // If the company survives the first full cycle starting from day L.
            if (T >= 0) {
                // If the net cycle change is non-negative, it will never bankrupt.
                cout << 0 << "\n";
            } else {
                // If the net cycle change is negative, it will eventually bankrupt.
                long long absT = -T;
                // Calculate how many full cycles q it takes before it enters a cycle where it bankrupts.
                // Bankruptcy condition: S + q*T + M < 0  =>  q*|T| > S + M
                long long q = (S + M) / absT + 1;
                long long S_prime = S + q * T;
                long long V = P_prev - S_prime;
                
                // Find the first day within the (q+1)-th cycle where bankruptcy happens.
                int idx = st.find_first(1, 0, 2 * N - 1, L - 1, L + N - 2, V);
                long long r = (long long)idx - L + 2;
                cout << (long long)q * N + r << "\n";
            }
        } else {
            // Bankruptcy occurs within the first cycle of N days.
            long long V = P_prev - S;
            int idx = st.find_first(1, 0, 2 * N - 1, L - 1, L + N - 2, V);
            long long r = (long long)idx - L + 2;
            cout << r << "\n";
        }
    }

    return 0;
}

---

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