概要

直線道路上を移動する \(N\) 台の山車すべてを収めるフレーム幅を最小化する撮影日を、\(0\) 日目から \(D\) 日目の中から選ぶ問題です。パラメータ変更が \(Q\) 回あり、各バージョンで最適解を求めます。

考察

F(d) の性質を見抜く

\(d\) 日目のフレーム幅は：

\[F(d) = \max_{i}(X_i + V_i \cdot d + L_i) - \min_{i}(X_i + V_i \cdot d - L_i)\]

ここで重要な観察があります：

• \(\max_{i}(X_i + V_i \cdot d + L_i)\) は 一次関数の最大値 → これは \(d\) に関して凸関数（折れ線の上側包絡線）
• \(\min_{i}(X_i + V_i \cdot d - L_i)\) は 一次関数の最小値 → これは \(d\) に関して凹関数（折れ線の下側包絡線）

したがって \(F(d) = (\text{凸関数}) - (\text{凹関数}) = (\text{凸関数}) + (\text{凸関数})\) となり、\(F(d)\) は凸関数です。

凸関数の最小値

凸関数は「谷型」の形状をしているため、区間 \([0, D]\) 上での最小値を効率的に求められます。全探索では \(O(D)\) かかり \(D \le 10^9\) なので TLE ですが、三分探索を使えば \(O(\log D)\) 回の評価で最小値が見つかります。

制約 \(N(Q+1) \le 5 \times 10^5\) の意味

各バージョンで \(F(d)\) を1回評価するのに \(O(N)\) かかります。全バージョン \((Q+1)\) 回の solve を行うので、1回の eval あたりの合計コストは \(O(N(Q+1) \cdot \log D)\) です。制約により \(N(Q+1)\) が \(5 \times 10^5\) に抑えられているため、十分高速です。

アルゴリズム

1. eval(d): 全山車をループして \(d\) 日目のフレーム幅 \(F(d)\) を \(O(N)\) で計算
2. solve(): 三分探索で凸関数 \(F(d)\) の最小値を求める
   • 区間 \([lo, hi]\) を三等分し、中間点 \(m_1, m_2\) で \(F\) を評価
   • \(F(m_1) \le F(m_2)\) なら最小値は \([lo, m_2]\) に、そうでなければ \([m_1, hi]\) にある
   • 区間幅が 3 未満になったら残りの候補をすべて調べる
3. 各修正後にパラメータを更新し、再度 solve() を呼ぶ

三分探索の直感的な説明

凸関数は最小値の左側で単調減少、右側で単調増加です。\(m_1 < m_2\) に対して \(F(m_1) > F(m_2)\) なら、最小値は \(m_1\) より右側にあるはずなので、\(lo = m_1\) と絞れます。逆の場合も同様です。

計算量

• 時間計算量: \(O(N(Q+1) \cdot \log D)\)
  • 三分探索は \(O(\log_{3/2} D) \approx 50\) 回の eval を行い、各 eval は \(O(N)\)
  • 全バージョン合計: \(5 \times 10^5 \times 50 \approx 2.5 \times 10^7\)
• 空間計算量: \(O(N)\)

実装のポイント

• 整数三分探索の終了条件: hi - lo >= 3 の間ループし、最後に残った数点を全探索する。整数の場合、区間が小さくなりすぎると三等分が正しく機能しないため、最後は全列挙が安全。

• オーバーフロー対策: \(V_i \cdot d\) が最大 \(10^6 \times 10^9 = 10^{15}\) になるため long long を使用。

• 更新処理: 配列を直接書き換えるだけで良い（各修正は累積的に反映される）。

  ソースコード

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, D, Q;
    cin >> N >> D >> Q;
    
    vector<long long> X(N), V(N), L(N);
    for(int i = 0; i < N; i++){
        cin >> X[i] >> V[i] >> L[i];
    }
    
    auto eval = [&](long long d) -> long long {
        long long mx = LLONG_MIN, mn = LLONG_MAX;
        for(int i = 0; i < N; i++){
            long long upper = X[i] + V[i]*d + L[i];
            long long lower = X[i] + V[i]*d - L[i];
            if(upper > mx) mx = upper;
            if(lower < mn) mn = lower;
        }
        return mx - mn;
    };
    
    auto solve = [&]() -> long long {
        long long lo = 0, hi = D;
        while(hi - lo >= 3){
            long long m1 = lo + (hi - lo) / 3;
            long long m2 = hi - (hi - lo) / 3;
            if(eval(m1) <= eval(m2)){
                hi = m2;
            } else {
                lo = m1;
            }
        }
        long long ans = LLONG_MAX;
        for(long long d = lo; d <= hi; d++){
            long long v = eval(d);
            if(v < ans) ans = v;
        }
        return ans;
    };
    
    cout << solve() << "\n";
    
    for(int q = 0; q < Q; q++){
        int p;
        long long a, b, c;
        cin >> p >> a >> b >> c;
        p--;
        X[p] = a;
        V[p] = b;
        L[p] = c;
        cout << solve() << "\n";
    }
    
    return 0;
}

---

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