アルゴリズムと数学 022

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_v

2つを足してある値になるは、ソートしてしゃくとり法ですね。

// Choose Cards 3
#![allow(non_snake_case)]

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()
}

fn groupby<T: PartialEq+Copy>(v: &Vec<T>) -> Vec<Vec<T>> {
    let mut vs = Vec::<Vec<T>>::new();
    let mut prev = Vec::<T>::new();
    for &e in v.iter() {
        match prev.last() {
            Some(&f) => if e != f {
                            vs.push(prev.clone());
                            prev.clear()
                        },
            None     => ()
        }
        prev.push(e)
    }
    vs.push(prev);
    return vs
}

fn f(A: &mut Vec<i32>, M: i32) -> usize {
    A.sort();
    let v = groupby(A).iter().map(|w| (w[0], w.len())).
                                collect::<Vec<(i32, usize)>>();
    let mut k = 0usize;
    let mut l = v.len() - 1;
    let mut counter = 0;
    while k < v.len() && l < A.len() {
        let (a1, n1) = v[k];
        let (a2, n2) = v[l];
        if a1 > a2 {
            break
        }
        if a1 + a2 == M {
            counter += if a1 != a2 { n1*n2 } else { n1*(n1-1)/2 };
            k += 1;
            l -= 1;
        }
        else if a1 + a2 < M {
            k += 1
        }
        else {
            l -= 1
        }
    }
    counter
}

fn main() {
    let _N: usize = read();
    let mut A = read_vec();
    println!("{}", f(&mut A, 100000))
}