概要

\(N\) 日サイクルの経営計画が無限に繰り返される中で、各クエリについて「初期資金 \(S\) で \(L\) 日目から経営を始めたとき、何日目に初めて倒産するか」を効率的に求める問題です。

考察

重要な気づき

各日の資金変動を \(D_i = A_i - B_i - C_i\) とし、累積和 \(P[i] = \sum_{k=1}^{i} D_k\) を定義します（\(P[0] = 0\)）。

\(L\) 日目から経営を始め初期資金が \(S\) のとき、\(L\) 日目から数えて \(k\) 日目（計画上の日 \(d\)）終了時の資金は： $\(S + P[d] - P[L-1]\)$ （同一サイクル内の場合）

倒産条件は \(S + P[d] - P[L-1] < 0\)、すなわち： $\(P[d] < P[L-1] - S\)$

サイクルの扱い

最初の不完全サイクル（\(L\) 日目〜\(N\) 日目）の後、\(m\) 回の完全サイクルを経た \((m+1)\) 回目の完全サイクル中の日 \(k\) での資金は： $\(S + (P[N] - P[L-1]) + m \cdot T + P[k] = S - P[L-1] + (m+1) \cdot T + P[k]\)$

ここで \(T = P[N]\)（1サイクルの純利益）。倒産条件は： $\(P[k] < P[L-1] - S - (m+1) \cdot T\)$

場合分け

• \(T \geq 0\) の場合：サイクルを重ねるほど閾値が下がるため、最初の不完全サイクルと最初の1回の完全サイクルだけ確認すればよい。どちらでも倒産しなければ永久に倒産しない。
• \(T < 0\) の場合：サイクルを重ねるほど閾値が上がり、いずれ必ず倒産する。どのサイクルで初めて倒産するかを計算で求める。

アルゴリズム

1. 前処理：累積和 \(P[i]\) を計算し、セグメント木に格納する。セグメント木は区間の最小値を管理し、「ある閾値未満の値を持つ最左の位置」を \(O(\log N)\) で求められるようにする。

2. 各クエリの処理：

   • 最初の不完全サイクル（\([L, N]\)）で \(P[k] < P[L-1] - S\) となる最左の \(k\) を探す。見つかれば答えは \(k - L + 1\)。
   • \(T \geq 0\) の場合：閾値 \(P[L-1] - S - T\) で \([1, N]\) を探索。見つかれば答えは \((N - L + 1) + k\)、見つからなければ \(0\)（倒産しない）。
   • \(T < 0\) の場合：\(P\) の全体最小値 \(\min P\) を使い、倒産が起こる最初のサイクル番号 \(m\) を \(O(1)\) で計算する： $\(m = \left\lfloor \frac{-(P[L-1] - S - \min P)}{-T} \right\rfloor\)\( そのサイクル内で閾値 \)P[L-1] - S - (m+1) \cdot T\( を用いて最左位置 \)k\( を見つけ、答えは \)(N - L + 1) + m \cdot N + k$。

計算量

• 時間計算量: \(O(N + Q \log N)\)
  • セグメント木の構築に \(O(N)\)、各クエリでセグメント木の探索に \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • セグメント木と累積和配列

実装のポイント

• 資金や累積和が非常に大きくなりうるため、long long を使用する（\(S\) は最大 \(10^{12}\)、累積和も大きくなる）。

• セグメント木で「閾値未満の最左位置」を探す際、該当なしの場合は \(-1\) を返す設計にする。

• \(T < 0\) の場合、\(m\) の計算で整数除算を正しく行う（\(R = P[L-1] - S - \min P\) が非負なら \(m = 0\)）。

• セグメント木のサイズを2冪に揃え、未使用部分は LLONG_MAX（十分大きい値）で初期化することで、範囲外の影響を防ぐ。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<long long> P(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        P[i] = P[i-1] + (a - b - c);
    }
    
    long long T = P[N];
    
    int sz = 1;
    while (sz < N) sz *= 2;
    vector<long long> tree(2 * sz, LLONG_MAX);
    for (int i = 1; i <= N; i++) {
        tree[sz + i - 1] = P[i];
    }
    for (int i = sz - 1; i >= 1; i--) {
        tree[i] = min(tree[2*i], tree[2*i+1]);
    }
    
    long long minP = tree[1];
    
    function<int(int, int, int, int, int, long long)> find_left = 
        [&](int node, int nl, int nr, int ql, int qr, long long thresh) -> int {
        if (nl > qr || nr < ql) return -1;
        if (tree[node] >= thresh) return -1;
        if (nl == nr) return nl;
        int mid = (nl + nr) / 2;
        int res = find_left(2*node, nl, mid, ql, qr, thresh);
        if (res != -1) return res;
        return find_left(2*node+1, mid+1, nr, ql, qr, thresh);
    };
    
    auto query = [&](int l, int r, long long threshold) -> int {
        return find_left(1, 1, sz, l, r, threshold);
    };
    
    for (int q = 0; q < Q; q++) {
        int L;
        long long S;
        cin >> L >> S;
        
        long long thresh1 = P[L-1] - S;
        int pos = query(L, N, thresh1);
        if (pos != -1) {
            cout << (pos - L + 1) << "\n";
            continue;
        }
        
        if (T >= 0) {
            long long thresh = P[L-1] - S - T;
            int pos2 = query(1, N, thresh);
            if (pos2 != -1) {
                cout << (long long)(N - L + 1) + pos2 << "\n";
            } else {
                cout << 0 << "\n";
            }
        } else {
            long long R = P[L-1] - S - minP;
            long long m;
            if (R >= 0) {
                m = 0;
            } else {
                m = (-R) / (-T);
            }
            long long thresh = P[L-1] - S - (m + 1) * T;
            int pos2 = query(1, N, thresh);
            long long answer = (long long)(N - L + 1) + (long long)m * N + pos2;
            cout << answer << "\n";
        }
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。