公式解説の判定問題を解くアルゴリズムの挙動についてさらに考察します。

\(H\) を固定したとき、以下のようなアルゴリズムを考えることができます。

はじめ、\((L,R)=(-\infty,\infty)\) とする。 \(i=1,2,\ldots,N\) について以下を繰り返す。

• 区間 \(I=[L-X,R+X]\cap[H-D _ i,U _ i]\) が空ならば、条件を満たす削り方は存在しない。
• 空でなければ \([L,R]=I\) となるよう \(L,R\) を更新する。

\(i=N\) まで処理が終了したら、条件を満たす削り方が存在する。

このアルゴリズムについて、\(H\) を動かしたときにそれぞれのステップでの \([L,R]\) の値がどのように変わるかを考えます。

\(H\) を少し小さくすると、すべての区間の下端も同じだけ小さくなることが観察によってわかります。 より厳密には、ある整数の \(2\) つ組の列 \(\bigl((u _ i,d _ i)\bigr) _ {i=1,2,\ldots,N}\) が存在して、\(i\) 番目の処理が終了した時点で（そこまでで区間が空になっていなければ）\((L,R)=(H-d _ i,u _ i)\) となることが示せます。

これが求められれば、\(H\) としてありえる最大の値を \(\displaystyle\min _i(u _ i+d _ i)\) と求めることができます。

判定問題を解くアルゴリズムで \((L,R)\) ではなく \((H-d,u)\) の組を管理していると考えることで、次のようなアルゴリズムで \(u _ i,d _ i\) を求めることができます。

はじめ、\(u=d=\infty\) とする。\(i=1,2,\ldots,N\) について以下を繰り返す。

• \(u\leftarrow\min\lbrace u+X,U _ i\rbrace,d\leftarrow\min\lbrace d+X,D _ i\rbrace\) と更新する。

上のアルゴリズムをそのまま実装することで、時間計算量を \(\Theta(N)\) 、空間計算量を \(\Theta(1)\) ワードとすることができます。

実装例は以下のようになります。

#include <iostream>

int main() {
    using namespace std;
    unsigned N, X;
    cin >> N >> X;
    
    unsigned long sum{};
    unsigned height{2000000000}, u{1000000000}, d{1000000000};
    for (unsigned i{}, U, D; i < N; ++i) {
        cin >> U >> D;
        sum += U;
        sum += D;
        u = min(u + X, U);
        d = min(d + X, D);
        height = min(height, u + d);
    }

    cout << sum - static_cast<unsigned long>(height) * N << endl;
    return 0;
}