概要

各日の資金増減を \(d_i=A_i-B_i-C_i\) として、周期的に繰り返される数列上で「累積資金が初めて負になる日」を各質問ごとに求めます。

累積和を \(2N\) 日分用意し、区間最小値と「初めてある値未満になる位置」をセグメント木で高速に求めます。

考察

まず、各日の資金増減を

\[ d_i = A_i - B_i - C_i \]

とします。

経営計画は周期 \(N\) で繰り返されるので、\(d_1,d_2,\ldots,d_N\) が無限に繰り返される数列だと考えられます。

質問で \(L\) 日目から始める場合、最初の \(N\) 日間は

\[ L,L+1,\ldots,N,1,2,\ldots,L-1 \]

という順番になります。

このような「途中から始まって一周する区間」を扱いやすくするために、数列を \(2\) 回並べた累積和を考えます。

累積和を

\[ p_0=0 \]

\[ p_i=p_{i-1}+d_{((i-1)\bmod N)+1} \]

とします。

すると、\(L\) 日目から始めたとき、経営開始から \(t\) 日後 \((1 \leq t \leq N)\) の資金増減は

\[ p_{L+t-1} - p_{L-1} \]

で表せます。

初期資金が \(S\) 円なので、倒産条件は

\[ S + p_{L+t-1} - p_{L-1} < 0 \]

です。

これを変形すると、

\[ p_{L+t-1} < p_{L-1} - S \]

となります。

つまり、区間 \([L, L+N-1]\) の中で、初めて累積和がある値未満になる位置を探せばよいです。

ただし、累積和は単調とは限らないため、単純な二分探索はできません。
また、各質問ごとに \(N\) 日分を調べると \(O(NQ)\) となり、最大で間に合いません。

そこで、セグメント木を使って次の操作を高速に行います。

• 区間の最小値を求める
• 区間内で初めて \(x\) 未満になる位置を求める

次に、\(1\) サイクル全体の増減を

\[ T = d_1+d_2+\cdots+d_N \]

とします。

\(T \geq 0\) の場合

\(1\) サイクル終わるごとに資金は減らないので、次のサイクルは前回と同じかそれ以上の資金で始まります。

したがって、最初の \(1\) サイクルで倒産しなければ、その後も倒産しません。

よって、区間 \([L,L+N-1]\) で

\[ p_k < p_{L-1}-S \]

となる最初の位置 \(k\) を探します。

見つかれば答えは

\[ k-L+1 \]

日目です。

見つからなければ答えは \(0\) です。

\(T < 0\) の場合

\(1\) サイクルごとに資金が減っていくので、いつか必ず倒産します。

ただし、初期資金 \(S\) が大きい場合、何サイクルも耐える可能性があります。
これを毎日シミュレーションすると間に合いません。

まず、\(L\) 日目から始めた \(1\) サイクル内での資金増減の最小値を求めます。

区間 \([L,L+N-1]\) における累積和の最小値を \(\min p_k\) とすると、\(1\) サイクル内での最悪の増減は

\[ m = \min_{k \in [L,L+N-1]} p_k - p_{L-1} \]

です。

\(c\) サイクル経過後にそのサイクルを始めると、開始時の資金は

\[ S + cT \]

です。

そのサイクル中の最小資金は

\[ S + cT + m \]

になります。

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

\(T<0\) なので、\(D=-T\) とすると、資金はサイクルごとに \(D\) 減ります。

もし

\[ S+m<0 \]

なら、最初のサイクルで倒産するので \(c=0\) です。

そうでなければ、

\[ c = \left\lfloor \frac{S+m}{D} \right\rfloor + 1 \]

です。

この \(c\) は「倒産が起こるサイクルの前に、何サイクル完了しているか」を表します。

そのサイクル内では、倒産条件は

\[ S+cT+p_k-p_{L-1}<0 \]

です。

変形すると、

\[ p_k < p_{L-1}-S-cT \]

となります。

再びセグメント木で、区間 \([L,L+N-1]\) の中からこの条件を初めて満たす位置 \(k\) を探します。

答えは

\[ cN + (k-L+1) \]

です。

アルゴリズム

1. 各日の増減 \(d_i=A_i-B_i-C_i\) を計算する。
2. 周期をまたぐ区間を扱うため、\(2N\) 日分の累積和 \(p\) を作る。
3. 累積和 \(p\) に対してセグメント木を構築する。
4. 各質問 \((L,S)\) について処理する。
   • \(base=p_{L-1}\)
   • \(R=L+N-1\)
   • \(T=p_N\)
5. \(T \geq 0\) の場合
   • \(p_k < base-S\) となる最初の \(k \in [L,R]\) を探す。
   • 見つかれば \(k-L+1\)、なければ \(0\) を出力する。
6. \(T < 0\) の場合
   • 区間 \([L,R]\) の最小値を求め、\(m=\min p_k-base\) とする。
   • 倒産が起こるサイクル番号 \(c\) を求める。
   • \(p_k < base-S-cT\) となる最初の \(k \in [L,R]\) を探す。
   • \(cN+(k-L+1)\) を出力する。

計算量

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

実装のポイント

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

\[ < 0 \]

です。

そのため、累積和を探すときも

\[ p_k < \text{limit} \]

という strict な不等号になります。
\( \leq \) にしてしまうと、資金がちょうど \(0\) 円の場合まで倒産扱いしてしまうので注意が必要です。

また、累積和や答えは大きくなる可能性があるため、long long を使います。

ソースコード

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

using ll = long long;
const ll INF = (1LL << 62);

struct SegTree {
    int n, m;
    vector<ll> seg;

    SegTree(const vector<ll>& a) {
        m = (int)a.size();
        n = 1;
        while (n < m) n <<= 1;
        seg.assign(2 * n, INF);
        for (int i = 0; i < m; i++) seg[n + i] = a[i];
        for (int i = n - 1; i >= 1; i--) {
            seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
        }
    }

    ll range_min(int l, int r) const {
        ll res = INF;
        l += n;
        r += n;
        while (l <= r) {
            if (l & 1) res = min(res, seg[l++]);
            if (!(r & 1)) res = min(res, seg[r--]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }

    int first_less_rec(int node, int nl, int nr, int ql, int qr, ll x) const {
        if (qr < nl || nr < ql || seg[node] >= x) return -1;
        if (nl == nr) return nl;
        int mid = (nl + nr) >> 1;
        int res = first_less_rec(node << 1, nl, mid, ql, qr, x);
        if (res != -1) return res;
        return first_less_rec(node << 1 | 1, mid + 1, nr, ql, qr, x);
    }

    int first_less(int l, int r, ll x) const {
        return first_less_rec(1, 0, n - 1, l, r, x);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<ll> d(N + 1);
    for (int i = 1; i <= N; i++) {
        ll A, B, C;
        cin >> A >> B >> C;
        d[i] = A - B - C;
    }

    vector<ll> pref(2 * N + 1, 0);
    for (int i = 1; i <= 2 * N; i++) {
        pref[i] = pref[i - 1] + d[(i - 1) % N + 1];
    }

    ll total = pref[N];
    SegTree seg(pref);

    while (Q--) {
        int L;
        ll S;
        cin >> L >> S;

        ll base = pref[L - 1];
        int R = L + N - 1;

        if (total >= 0) {
            ll limit = base - S;
            int idx = seg.first_less(L, R, limit);
            if (idx == -1) {
                cout << 0 << '\n';
            } else {
                cout << (ll)(idx - L + 1) << '\n';
            }
        } else {
            ll min_pref = seg.range_min(L, R);
            ll mn = min_pref - base;

            ll cycles = 0;
            ll val = S + mn;
            if (val >= 0) {
                ll dec = -total;
                cycles = val / dec + 1;
            }

            ll threshold = -S - cycles * total;
            ll limit = base + threshold;
            int idx = seg.first_less(L, R, limit);

            ll ans = cycles * (ll)N + (ll)(idx - L + 1);
            cout << ans << '\n';
        }
    }

    return 0;
}

---

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