AtCoder Beginner Contest 457 D

https://atcoder.jp/contests/abc457/tasks/abc457_d

値の下限を決めて、そこに達するまで何回操作するかを調べます。そして、二分探索でその下限を決めます。ただし、細かいところがややこしいですね。

// Raise Minimum
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (i64, Vec<i64>) {
    let v: Vec<i64> = read_vec();
    let K = v[1];
    let A: Vec<i64> = read_vec();
    (K, A)
}

// 最小がL以上になる最小の回数と実際の最小
fn min_turns(L: i64, B: &Vec<(i64, i64)>) -> (i64, i64) {
    let mut counter: i64 = 0;
    let mut min_value: i64 = i64::MAX;
    for &(a, i) in B.iter() {
        if a >= L {
            if min_value == i64::MAX {
                min_value = min_value.min(a)
            }
            break
        }
        let turn = (L - a + i - 1) / i;
        counter += turn;
        min_value = min_value.min(a + i * turn)
    }
    (counter, min_value)
}

fn F_finally(c: i64, K: i64, B: &Vec<(i64, i64)>) -> i64 {
    // cになるものを探す
    let mut indices: Vec<i64> = vec![];
    let mut counter: i64 = 0;
    let mut min_value: i64 = i64::MAX;  // c以外の最小の値
    for &(a, i) in B.iter() {
        if a > c {
            break
        }
        let turn = (c - a + i - 1) / i;
        let value = a + turn * i;
        counter += turn;
        if value == c {
            indices.push(i)
        }
        else {
            min_value = min_value.min(value)
        }
    }
    
    indices.sort();
    let res = (K - counter) as usize;
    if res < indices.len() {
        c
    }
    else {
        let value = c + indices[0];
        min_value.min(value)
    }
}

fn F(K: i64, A: Vec<i64>) -> i64 {
    let mut B: Vec<(i64, i64)> = A.into_iter().enumerate().
                                    map(|(i, a)| (a, (i+1) as i64)).collect();
    B.sort();
    let mut first: i64 = 1;
    loop {
        let (k, c) = min_turns(first, &B);
        if k == K {
            return c
        }
        else if k > K {
            break
        }
        first *= 2
    }
    
    let mut last = first;
    first = first / 2;
    while last - first > 1 {
        let mid = (first + last) / 2;
        let (k, c) = min_turns(mid, &B);
        if k == K {
            return c
        }
        else if k < K {
            first = mid
        }
        else {
            last = mid
        }
    }
    
    // 複数が同時にcになっている
    F_finally(first, K, &B)
}

fn main() {
    let (K, A) = read_input();
    println!("{}", F(K, A))
}