概要

各日の資金増減 \(A_i-B_i-C_i\) が周期 \(N\) で無限に繰り返されます。
各質問について、指定された日から始めたときに、累積資金が初めて負になる日を高速に求めます。

考察

まず、各日の資金増減を

\[ D_i = A_i - B_i - C_i \]

とします。

質問ごとに実際に 1 日ずつシミュレーションすると、倒産まで非常に長い日数がかかる可能性があります。
また、\(Q\) 個の質問それぞれで最大 \(N\) 日ぶん調べるだけでも、最悪で \(O(NQ)\) となり、\(N+Q \leq 2 \times 10^5\) では間に合いません。

重要なのは、経営計画は周期 \(N\) で繰り返されることです。

開始日を \(L\)、0-indexed で \(s=L-1\) とします。
開始から \(k\) 日後までの資金増加量は、循環列上で

\[ D_s + D_{s+1} + \cdots + D_{s+k-1} \]

です。

これを高速に求めるために、配列 \(D\) を 2 回並べたものの累積和を作ります。

累積和を \(P\) とすると、開始日 \(s\) から \(k\) 日後までの増加量は

\[ P_{s+k} - P_s \]

で表せます。

---

まず、開始から最初の \(N\) 日間、つまり 1 周分だけを考えます。

その 1 周の中で最も資金が少なくなる増加量を

\[ \min_{1 \leq k \leq N} (P_{s+k} - P_s) \]

とします。

この値を \(\mathrm{mn}\) とします。

初期資金が \(S\) なら、1 周目の途中での最低資金は

\[ S + \mathrm{mn} \]

です。

• もし \(S+\mathrm{mn}<0\) なら、倒産は 1 周目の中で起こります。
• そうでない場合、1 周目では倒産しません。

次に、1 周全体の資金増加量を

\[ T = D_1 + D_2 + \cdots + D_N \]

とします。

1 周目で倒産しない場合、

• \(T \geq 0\) なら、周回を重ねても開始時の資金は減らないので、今後も倒産しません。
• \(T < 0\) なら、1 周するたびに資金が \(-T\) 円ずつ減るので、いつか倒産します。

---

倒産する具体的な日を求めるには、「ある範囲の累積和の中で、初めてある値未満になる位置」を探す必要があります。

累積和列は単調とは限らないため、二分探索は使えません。
そこで、累積和列に対して区間最小値を持つセグメント木を作り、

• 区間最小値を求める
• 区間内で初めて指定値未満になる位置を探す

ことを高速に行います。

アルゴリズム

1. 前処理

各日の増減を

\[ D_i = A_i - B_i - C_i \]

として配列に保存します。

次に、\(D\) を 2 回繰り返した長さ \(2N\) の列について累積和 \(P\) を作ります。

\[ P_0 = 0 \]

\[ P_{i+1} = P_i + D_{i \bmod N} \]

とします。

これにより、任意の開始位置 \(s\) から最大 \(N\) 日分の累積増加量を、連続区間として扱えます。

また、1 周全体の増加量を

\[ T = P_N \]

とします。

累積和 \(P\) に対して、区間最小値を管理するセグメント木を構築します。

---

2. 各質問の処理

質問で開始日 \(L\)、初期資金 \(S\) が与えられたとします。
0-indexed の開始位置を

\[ s = L - 1 \]

とします。

1 周分に対応する累積和の範囲は

\[ P_{s+1}, P_{s+2}, \ldots, P_{s+N} \]

です。

コード上では半開区間で

\[ [s+1, s+N+1) \]

を見ます。

この範囲の最小値をセグメント木で求めます。

\[ \mathrm{mn} = \min(P_{s+1}, \ldots, P_{s+N}) - P_s \]

これは「開始から 1 周以内での資金増加量の最小値」です。

---

3. 1 周目で倒産する場合

もし

\[ S + \mathrm{mn} < 0 \]

なら、1 周目のどこかで倒産します。

倒産条件は、ある \(k\) について

\[ S + (P_{s+k} - P_s) < 0 \]

です。

変形すると、

\[ P_{s+k} < P_s - S \]

です。

したがって、区間 \([s+1, s+N+1)\) の中で初めて

\[ P_i < P_s - S \]

となる位置 \(i\) を探します。

答えは

\[ i - s \]

日目です。

---

4. 1 周目で倒産しない場合

1 周目で倒産しないなら、次に \(T\) を見ます。

\(T \geq 0\) の場合

1 周するたびに資金は減らないため、以後も倒産しません。

答えは 0 です。

\(T < 0\) の場合

1 周するたびに資金が \(d=-T\) だけ減ります。

\(c\) 周終わった後の資金は

\[ S - cd \]

です。

その周の中での最低資金は

\[ S - cd + \mathrm{mn} \]

です。

これが初めて負になる最小の \(c\) を求めます。

\[ S - cd + \mathrm{mn} < 0 \]

\[ cd > S + \mathrm{mn} \]

なので、

\[ c = \left\lfloor \frac{S+\mathrm{mn}}{d} \right\rfloor + 1 \]

です。

つまり、\(c\) 周分は丸ごと進めたあと、その次の周の中で倒産します。

その時点での資金は

\[ S + cT \]

です。

この資金を \(\mathrm{capital}\) とすると、倒産条件は

\[ \mathrm{capital} + (P_i - P_s) < 0 \]

すなわち

\[ P_i < P_s - \mathrm{capital} \]

です。

再びセグメント木を使って、区間 \([s+1, s+N+1)\) の中で初めてこの条件を満たす位置 \(i\) を探します。

答えは

\[ cN + (i-s) \]

です。

計算量

• 時間計算量: \(O((N+Q)\log N)\)
• 空間計算量: \(O(N)\)

セグメント木の構築に \(O(N)\)、各質問で区間最小値取得と「初めて閾値未満になる位置」の探索を行うため \(O(\log N)\) です。

実装のポイント

倒産条件は「資金が \(0\) 円未満」なので、判定は <= ではなく < です。

例えば、資金がちょうど \(0\) 円になっても倒産ではありません。

そのため、位置を探す条件も

\[ P_i < P_s - S \]

のように、厳密な不等号になります。

また、累積和や答えの日数は大きくなる可能性があります。
Python では整数が任意精度なので問題ありませんが、C++ などで実装する場合は long long を使う必要があります。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    Q = next(it)

    diff = [0] * N
    for i in range(N):
        a = next(it)
        b = next(it)
        c = next(it)
        diff[i] = a - b - c

    M = 2 * N + 1
    pref = [0] * M
    for i in range(2 * N):
        pref[i + 1] = pref[i] + diff[i % N]

    total = pref[N]

    INF = 10**30
    size = 1
    while size < M:
        size <<= 1

    seg = [INF] * (2 * size)
    seg[size:size + M] = pref

    for i in range(size - 1, 0, -1):
        v1 = seg[i << 1]
        v2 = seg[i << 1 | 1]
        seg[i] = v1 if v1 < v2 else v2

    def range_min(l, r):
        l += size
        r += size
        res = INF
        sg = seg
        while l < r:
            if l & 1:
                if sg[l] < res:
                    res = sg[l]
                l += 1
            if r & 1:
                r -= 1
                if sg[r] < res:
                    res = sg[r]
            l >>= 1
            r >>= 1
        return res

    def first_less(l, r, x):
        l += size
        r += size
        left = []
        right = []
        sg = seg

        while l < r:
            if l & 1:
                left.append(l)
                l += 1
            if r & 1:
                r -= 1
                right.append(r)
            l >>= 1
            r >>= 1

        for node in left:
            if sg[node] < x:
                while node < size:
                    lc = node << 1
                    if sg[lc] < x:
                        node = lc
                    else:
                        node = lc | 1
                return node - size

        for node in reversed(right):
            if sg[node] < x:
                while node < size:
                    lc = node << 1
                    if sg[lc] < x:
                        node = lc
                    else:
                        node = lc | 1
                return node - size

        return -1

    ans = []
    for _ in range(Q):
        L = next(it)
        S = next(it)

        s = L - 1
        base = pref[s]
        l = s + 1
        r = s + N + 1

        mn = range_min(l, r) - base

        if S + mn < 0:
            threshold = base - S
            idx = first_less(l, r, threshold)
            ans.append(str(idx - s))
        else:
            if total >= 0:
                ans.append("0")
            else:
                d = -total
                cycles = (S + mn) // d + 1
                capital = S + cycles * total
                threshold = base - capital
                idx = first_less(l, r, threshold)
                ans.append(str(cycles * N + (idx - s)))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。