AtCoder Beginner Contest 392 D

https://atcoder.jp/contests/abc392/tasks/abc392_d

総当たりするだけですね。ただし、同じ値はHashMapでまとめておきます。

// Doubles
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// 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() -> Vec<Vec<i32>> {
    let N: usize = read();
    let mut A: Vec<Vec<i32>> = vec![vec![]; N];
    for i in 0..N {
        let v: Vec<i32> = read_vec();
        for &a in &v[1..] {
            A[i].push(a)
        }
    }
    A
}

fn frequency(v: &Vec<i32>) -> HashMap<i32, f64> {
    let K = v.len();
    let mut freq: HashMap<i32, f64> = HashMap::new();
    for &a in v {
        let e = freq.entry(a).or_insert(0.0);
        *e += 1.0 / (K as f64)
    }
    freq
}

fn prob(freq1: &HashMap<i32, f64>, freq2: &HashMap<i32, f64>) -> f64 {
    let mut total_p = 0.0;
    for (&n, &p1) in freq1 {
        if let Some(&p2) = freq2.get(&n) {
            total_p += p1 * p2
        }
    }
    total_p
}

fn F(A: Vec<Vec<i32>>) -> f64 {
    let N = A.len();
    let freqs: Vec<HashMap<i32, f64>> = A.iter().map(|v| frequency(v)).
                                                                collect();
    
    let mut max_p = 0.0;
    for i in 0..N-1 {
        for k in i+1..N {
            let p = prob(&freqs[i], &freqs[k]);
            if p > max_p {
                max_p = p
            }
        }
    }
    max_p
}

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