AGC041 C - Domino Quality
問題
コンテスト中の解法
- 実験すると雑な全探索でn=4, 5, 6が求まる。n=7は計算が終わらなかった。これを組み合わせるとn=7以外は構築可能になる。
- n=7を気合で手作りする。
コンテスト後の解法
全探索を高速化してn=7を求めたい。
- 縦向きのドミノと横向きのドミノが同数であることが分かる。
- 縦向きのドミノの個数をx、横向きのものをyとすると、各ドミノの行へのクオリティの寄与の合計は2x+y、各ドミノの列へのクオリティの寄与の合計はx+2yなので、x+2y=2x+yよりx=yである。
- n=7のとき縦横各7枚ずつのドミノが必要になる。
- まず縦に7枚置き、次に空いているところに横に7枚置く全探索で十分高速にn=7が求まる。
コード
use std::collections::BTreeSet; const S4: [[char; 4]; 4] = [ ['a', 'b', 'e', 'e'], ['a', 'b', 'f', 'f'], ['g', 'g', 'c', 'd'], ['h', 'h', 'c', 'd'], ]; const S5: [[char; 5]; 5] = [ ['a', 'c', 'd', '.', '.'], ['a', 'c', 'd', '.', '.'], ['b', 'f', 'f', 'g', 'g'], ['b', '.', 'e', 'h', 'h'], ['i', 'i', 'e', 'j', 'j'], ]; const S6: [[char; 6]; 6] = [ ['a', 'd', 'g', 'g', '.', '.'], ['a', 'd', 'h', 'h', '.', '.'], ['b', 'e', 'i', 'i', '.', '.'], ['b', 'e', '.', '.', 'j', 'j'], ['c', 'f', '.', '.', 'k', 'k'], ['c', 'f', '.', '.', 'l', 'l'], ]; const S7: [[char; 7]; 7] = [ ['a', 'd', 'f', '.', '.', '.', '.'], ['a', 'd', 'f', '.', '.', '.', '.'], ['b', 'e', 'g', '.', '.', '.', '.'], ['b', 'e', 'g', '.', '.', '.', '.'], ['c', '.', '.', 'h', 'h', 'i', 'i'], ['c', '.', '.', 'j', 'j', 'k', 'k'], ['.', 'l', 'l', 'm', 'm', 'n', 'n'], ]; fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock()); let n: usize = sc.read(); if n == 2 { println!("-1"); return; } else if n == 3 { sc.write("aa.\n"); sc.write("..b\n"); sc.write("..b\n"); return; } let mut ans = vec![vec!['.'; n]; n]; let m = n / 4; for k in 0..m { for i in 0..4 { for j in 0..4 { ans[k * 4 + i][k * 4 + j] = S4[i][j]; } } } match n % 4 { 0 => {} 1 => { assert!(n >= 5); for i in 0..5 { for j in 0..5 { ans[n - 5 + i][n - 5 + j] = S5[i][j]; } } } 2 => { assert!(n >= 6); for i in 0..6 { for j in 0..6 { ans[n - 6 + i][n - 6 + j] = S6[i][j]; } } } 3 => { assert!(n >= 7); for i in 0..7 { for j in 0..7 { ans[n - 7 + i][n - 7 + j] = S7[i][j]; } } } _ => unreachable!(), } for i in 0..n { for j in 0..n { sc.write(format!("{}", ans[i][j])); } sc.write("\n"); } } fn naive(n: usize) -> Vec<Vec<char>> { let mut map = vec![vec!['.'; n]; n]; if put(0, 0, &mut map, true) { map } else { unreachable!(); } } fn put(depth: usize, pos: usize, map: &mut Vec<Vec<char>>, first: bool) -> bool { let n = map.len(); if depth == n { if first { rotate(map); if put(0, 0, map, false) { return true; } rotate(map); return false; } else { return is_valid(map); } } for pos in pos..(n * n) { let i = pos / n; let j = pos % n; if j + 1 < n && map[i][j] == '.' && map[i][j + 1] == '.' { let c = (depth as u8 + 'a' as u8 + if first { 0 } else { n as u8 }) as char; map[i][j] = c; map[i][j + 1] = c; if put(depth + 1, pos + 1, map, first) { return true; } map[i][j] = '.'; map[i][j + 1] = '.'; } } false } fn rotate(map: &mut Vec<Vec<char>>) { let n = map.len(); let clone = map.clone(); for i in 0..n { for j in 0..n { map[i][j] = clone[j][i]; } } } fn is_valid(map: &Vec<Vec<char>>) -> bool { let n = map.len(); for row in 0..n { let mut set = BTreeSet::new(); for col in 0..n { if map[row][col] == '.' { continue; } set.insert(map[row][col]); } if set.len() != 3 { return false; } } for col in 0..n { let mut set = BTreeSet::new(); for row in 0..n { if map[row][col] == '.' { continue; } set.insert(map[row][col]); } if set.len() != 3 { return false; } } true } pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>); impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> IO<R, W> { IO(r, std::io::BufWriter::new(w)) } pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) { use std::io::Write; self.1.write(s.as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }