AGC041 C - Domino Quality

問題

atcoder.jp

コンテスト中の解法

  • 実験すると雑な全探索で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()
    }
}