bouzuya.hatenablog.com

ぼうずやのにっき

ABC077 C を解いた

bouzuya/rust-atcoder でふと target/ を共有できるかもと思い cargo workspace を使用するように変更してみた。明日また試す。

  • Snuke Festival (AtCoder Beginner Contest 077:C問題) https://atcoder.jp/contests/abc077/tasks/arc084_a
    • https://atcoder.jp/contests/abc077/submissions/43469359
    • 変数が3つあるときは真ん中を固定、のやつ
    • B_i を走査 (固定) する
    • B_i 未満の個数と B_i + 1 以上の個数を得られれば掛けてその B_i のときの個数が分かる
    • B_i 未満の個数は A をソートしておけば二分探索で求められる
    • 同様に B_i + 1 以上の個数も C をソートしておけば二分探索で求められる
    • 各 B_i のときの個数の和が答えになる
use proconio::input;
use superslice::Ext;

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

    let mut sum = 0_usize;
    for b_i in b {
        let count_a = a.lower_bound(&b_i);
        let count_b = n - c.lower_bound(&(b_i + 1));
        sum += count_a * count_b;
    }
    let ans = sum;
    println!("{}", ans);
}

今日のコミット。