https://atcoder.jp/contests/abc315/tasks/abc315_d
題意どおりに組めばいいだけですが、Rustだとめんどうですね。
// Magical Cookies #![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 //////////////////// type Table = Vec<Vec<char>>; type CharFreq = HashMap<usize, HashMap<char, i32>>; fn read_input() -> Table { let v = read_vec(); let H: usize = v[0]; (0..H).map(|_| read::<String>()). map(|s| s.chars().collect::<Vec<char>>()). collect::<Table>() } fn collect_chars_row(row: &Vec<char>) -> HashMap<char, i32> { let mut counter: HashMap<char, i32> = HashMap::new(); for &c in row.iter() { let e = counter.entry(c).or_insert(0); *e += 1 } counter } fn collect_chars_col(i: usize, table: &Table) -> HashMap<char, i32> { let mut counter: HashMap<char, i32> = HashMap::new(); for row in table.iter() { let c = row[i]; let e = counter.entry(c).or_insert(0); *e += 1 } counter } fn get_char(m: &HashMap<char, i32>) -> char { for c in m.keys() { return *c } 'a' } fn count_chars(chars: &Vec<(usize, char)>) -> HashMap<char, i32> { let mut freq_chars: HashMap<char, i32> = HashMap::new(); for &(_, c) in chars.iter() { let e = freq_chars.entry(c).or_insert(0); *e += 1 } freq_chars } fn f(table: Table) -> i32 { let H = table.len(); let W = table[0].len(); let mut rows = (0..H).map(|i| (i, collect_chars_row(&table[i]))). collect::<CharFreq>(); let mut cols = (0..W).map(|i| (i, collect_chars_col(i, &table))). collect::<CharFreq>(); loop { let row_removed: Vec<(usize, char)> = rows.iter(). filter(|(_, m)| m.len() == 1 && cols.len() > 1). map(|(i, r)| (*i, get_char(r))).collect(); let col_removed: Vec<(usize, char)> = cols.iter(). filter(|(_, r)| r.len() == 1 && rows.len() > 1). map(|(i, r)| (*i, get_char(r))).collect(); if row_removed.is_empty() && col_removed.is_empty() { break } for &(i, _) in row_removed.iter() { rows.remove(&i); } for &(i, _) in col_removed.iter() { cols.remove(&i); } let row_chars = count_chars(&row_removed); let col_chars = count_chars(&col_removed); for v in cols.values_mut() { for (&c, &f) in row_chars.iter() { let e = v.entry(c).or_insert(0); *e -= f; if *e == 0 { v.remove(&c); } } } for v in rows.values_mut() { for (&c, &f) in col_chars.iter() { let e = v.entry(c).or_insert(0); *e -= f; if *e == 0 { v.remove(&c); } } } } rows.iter().map(|(_, f)| f.values().sum::<i32>()).sum::<i32>() } //////////////////// main //////////////////// fn main() { let table = read_input(); println!("{}", f(table)) }