Codeforces I. Photo Processing (2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest)

問題文

http://codeforces.com/problemset/problem/883/I

解法

求めたい値は二分探索で求めましょう．
あとはある x にたいして題意を満たす分割が可能か調べます．
写真の値はソートしておくと，題意の分割は連続部分列の分割になります．
その上で，以下の累積和を考えます．
dp[i] := 写真 [0..j] ( j <= i ) だけを考えた時，題意を満たす分割が可能な j の個数

写真 i について考えます．この写真は少なくとも i - k より左にある写真を含むような列に含まれなければなりません．また，vi - x 以上である値を持つ最も左の写真より左側の写真を一緒に含めることも出来ません．
r = i - k，l = (vi - x 以上の最も左の写真の位置) とすると，l から r の間でうまく分割できれば，この写真を分割することができます．
これは先程の累積和を使って言い換えると，l から r の間に dp[j] != dp[j + 1] となるような位置があれば良いということになります．
したがって，dp[l - 1] と dp[r] の値を比べて，それらが違えば間に分割できる位置があると判定することが出来ます．

計算量は O(N log V) です．

ソースコード

fn lower_bound<T: Ord>(v: &Vec<T>, first: usize, last: usize, val: T) -> usize {
    let (mut lb, mut ub) = (first, last);
    while ub - lb > 0 {
        let mid = (ub + lb) / 2;
        if v[mid] < val {
            lb = mid + 1;
        } else {
            ub = mid;
        }
    }
    return ub;
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let n: usize = sc.read();
    let k: usize = sc.read();
    let mut v: Vec<i32> = vec![0; n + 1];
    for i in 1..n+1 {
        v[i] = sc.read();
    }
    v.sort();
    let v = v;

    let (mut lb, mut ub): (i32, i32) = (-1, 1e9 as i32);
    while ub - lb > 1 {
        let mid = (lb + ub) / 2;
        let mut dp: Vec<i32> = vec![0; n + 1];
        dp[0] = 1;
        for i in 1..n+1 {
            dp[i] = dp[i - 1];
            let l = lower_bound(&v, 1, n + 1, v[i] - mid) - 1;
            if i < k {
                continue;
            }
            let r = i - k;
            if r >= l && dp[r] > if l > 0 { dp[l - 1] } else { 0 } {
                dp[i] += 1;
            }
        }
        if dp[n] == dp[n - 1] {
            lb = mid;
        } else {
            ub = mid;
        }
    }
    println!("{}", ub);
}