問題

https://atcoder.jp/contests/arc037/tasks/arc037_c

解法

まずはナイーブに全探索を実装することを考える。

// https://atcoder.jp/contests/arc037/tasks/arc037_c

use proconio::input;

fn main() {
    input! {
        n: i64,
        k: i64,
        mut a: [i64; n],
        mut b: [i64; n],
    }
    let mut x = vec![];
    for aa in &a {
        for bb in &b {
            x.push(aa*bb)
        }
    }
    x.sort();
    println!("{}", x[(k-1) as usize])
}

この場合、次のような計算量となる。

行列を配列xに平坦化する処理: O(n²)
平坦化した配列xをソートする処理: O(n² logn)

1 ≦ N ≦ 30000 であるため、この計算量だと 10⁸ を若干超えてしまう。リソースの乏しいジャッジサーバの悲痛な叫びが聞こえてくる、そんな数字だ。 1812年のロシア遠征で無謀な行軍をしたナポレオンのように、一か八かの賭けに臣下を巻き添えにしてはならない。我々は領土欲、名誉欲に眩んだとしても、決して綱渡り的遠征、綱渡り的全探索など行うべきではないのだ。

どのように計算量を削減するか。「x番目の最小値 / 最大値」を求める問題は、二分探索によって効率的に求めることができる。

すなわち、本問題を「 N² 個の整数のうち、K番目に小さい値を求める」 => 「 N² 個の整数のうち、値が x 以下となる整数の個数が K となるような x の最小値を求める」と言い換えて考える。（x以下となる整数の数がK以上となるxの最小値 = 数がKとなる上限 = 小さい方からK番目の数）

// https://atcoder.jp/contests/arc037/tasks/arc037_c

use proconio::input;

const INF: i64 = 1<<60;

fn check(a: &Vec<i64>, b: &Vec<i64>, x: i64, k: usize) -> bool {
    let mut cnt = 0;
    let mut j = 0;
    for a in a.iter().rev() {
        while j < b.len() && *a * b[j] <= x {
            j += 1;
        }
        cnt += j;
    }
    return cnt >= k
}

fn main() {
    input! {
        n: i64,
        k: i64,
        mut a: [i64; n],
        mut b: [i64; n],
    }
    a.sort();
    b.sort();

    let mut left = 0;
    let mut right = INF;

    // 'k' th minimum value
    // => minimum x | the number of value that satisfy < x is K in []a*b
    // in this case, x is the upper bound of []a*b which satisfy 'k' th minimum value
    while right - left > 1 {
        let mid = (left + right) / 2;
        if check(&a, &b, mid, k as usize) {
            right = mid
        } else {
            left = mid
        }
    }
    println!("{}", right)
}

二分探索、という言葉を字句通り受け取れば、単なる中間値を参照・比較して目的の値を見つける探索手段のように思えるが、実は「**となる上限/下限の最小値/最大値を求める」ことで目的の解を得るというロジック、これこそに、この探索法のエッセンスが詰まっていると僕は思う。

2sec

2秒間でライムを刻め

ARC037 C 億マス計算

問題

解法