第一回日本最強プログラマー学生選手権決勝 D

問題

長さ $N$ の整数列 $(L_i), (R_i)$ が与えられる。各 $K = 2, \cdots, N$ について以下の問題に答えよ。

長さ $K$ の整数列 $(X_i)$ を考える。ただし各 $1 \leq i \leq K$ について $L_i \leq X_i \leq R_i$ を満たしていなくてはならない。そのような $(X_i)$ のうち、 $\max_{1 \leq i \lt K} \{ X_{i+1} - X_i \}$ の最小値を求めよ。

制約

$1 \leq N \leq 2 \cdot 10^5$
$0 \leq L_i \leq R_i \leq 10^9$

考察

$D = \max_{1 \leq i \lt K} \{ X_{i+1} - X_i \}$ を二分探索することを考える。

$D$ を固定すると、 $X_{i+1} \leq X_i + D$ が制約として加わる。 $L_i \leq X_i$ に違反しないためには、 $X_i$ は取りうる最大値を取るのが最善となる。よって最善な $X_i$ は以下の漸化式で表される。

$X_1 = R_1$
$X_i = \min(R_i, X_{i-1} + D) \quad (i \geq 2)$

さらにこれを整理すると、以下のように表せる。

$$ X_i = \min_{1 \leq j \leq i} \{ R_j + D (i - j) \} $$

$i$ を $\min$ から括りだすと以下の通り。

$$ Y_i = X_i - D \cdot i = \min_{1 \leq j \leq i} \{ R_j - D \cdot j \} $$

したがって $D$ に対する解が存在する必要十分条件は、「任意の $1 \leq i \leq K$ について $L_i - D \cdot i \leq Y_i$ が成り立つこと」となる。

二分探索の下界を直前の $D$ の値にすれば、解の単調性より $i \lt K$ についての条件は必ず満たされる。よって $L_K - D \cdot K \leq Y_K$ かどうかが高速に判定できれば良いが、 $Y_K = \min_{1 \leq j \leq K} \{ R_j - D \cdot j \}$ は愚直に計算すると $\Theta(K)$ かかってしまう。

ここで $R_j - D \cdot j$ が $D$ についての 1 次関数であることに着目すると、Convex Hull Trickによって $Y_K$ は $O(\log K)$ で求めることができる。今回は傾き $-j$ が単調減少なので、直線の追加は均し $O(1)$ でできる。

実装例

提出 #17572138 - 第一回日本最強プログラマー学生選手権決勝

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#include <iostream>
#include <vector>

template <class T>
struct ConvexHullTrick { ... };

using lint = long long;
constexpr lint INF = 1 << 30;

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::pair<lint, lint>> ps(n);
    for (auto& [l, r] : ps) std::cin >> l;
    for (auto& [l, r] : ps) std::cin >> r;

    ConvexHullTrick<lint> cht;
    lint ans = -INF;

    for (int i = 0; i < n; ++i) {
        auto [l, r] = ps[i];
        cht.add(i, r);
        if (i == 0) continue;

        lint ok = INF, ng = ans - 1;  // 二分探索の下界をansに
        while (ok - ng > 1) {
            lint x = (ok + ng) / 2;

            if (l - x * i <= cht(-x)) {
                ok = x;
            } else {
                ng = x;
            }
        }

        ans = ok;
        std::cout << ans << "\n";
    }
}