https://atcoder.jp/contests/abc337/tasks/abc337_d
1行ごとにDPで最小値を求めます。
// Cheating Gomoku Narabe #![allow(non_snake_case)] use std::cmp::min; //////////////////// 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>>; fn read_input() -> (usize, Vec<String>) { let v: Vec<usize> = read_vec(); let (H, K) = (v[0], v[2]); let S: Vec<String> = (0..H).map(|_| read::<String>()).collect(); (K, S) } fn transpose(table: &Table) -> Table { let H = table.len(); let W = table[0].len(); (0..W).map(|j| (0..H).map(|i| table[i][j]).collect::<Vec<char>>()). collect::<Table>() } fn get_min_plays(num_x: usize, num_o: usize, K: usize) -> usize { if num_x == 0 { K - num_o } else { K + 1 } } fn find_min_plays_each(v: &Vec<char>, K: usize) -> usize { let mut num_x = (0..K).filter(|&j| v[j] == 'x').count(); let mut num_o = (0..K).filter(|&j| v[j] == 'o').count(); let mut min_plays = get_min_plays(num_x, num_o, K); for j in K..v.len() { match v[j-K] { 'x' => num_x -= 1, 'o' => num_o -= 1, _ => () } match v[j] { 'x' => num_x += 1, 'o' => num_o += 1, _ => () } min_plays = min(min_plays, get_min_plays(num_x, num_o, K)) } min_plays } fn find_min_plays(table: &Table, K: usize) -> usize { if table[0].len() < K { return K + 1 } let mut min_plays = K + 1; for v in table.iter() { min_plays = min(min_plays, find_min_plays_each(v, K)) } min_plays } fn F(K: usize, S: Vec<String>) -> i32 { let table: Table = S.into_iter(). map(|s| s.chars().collect::<Vec<char>>()).collect(); let min_plays1 = find_min_plays(&table, K); let table_t = transpose(&table); let min_plays2 = find_min_plays(&table_t, K); let min_plays = min(min_plays1, min_plays2); if min_plays == K + 1 { -1 } else { min_plays as i32 } } fn main() { let (K, S) = read_input(); println!("{}", F(K, S)) }