今日解いた問題

atcoder.jp

バグらせずに実装するのが地味に大変な問題だと思う。

use std::cmp;
use std::collections::BTreeMap;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };

    let h: usize = sc.read();
    let w: usize = sc.read();
    let mut board = vec![vec![false; w]; h];
    for i in 0..h {
        let s = sc.chars();
        for j in 0..w {
            board[i][j] = s[j] == '#';
        }
    }

    let mut inv_board = vec![vec![false; w]; h];
    for i in 0..h {
        for j in 0..w {
            inv_board[i][j] = board[h - 1 - i][j];
        }
    }

    let ans1 = solve(&board);
    let ans2 = solve(&inv_board);

    let mut ans = ans1 + ans2;
    let mut map = BTreeMap::new();
    for x in 0..h {
        for y in 0..w {
            if board[x][y] {
                // y = -x + l
                let l = x + y;
                map.entry(l).or_insert(Vec::new()).push((x, y));
            }
        }
    }

    for v in map.values() {
        for j in 0..v.len() {
            for i in 0..j {
                let (x1, y1) = v[i];
                let (x2, y2) = v[j];
                let d = y1 - y2;

                let mut c = vec![];
                if x1 >= d {
                    c.push((x1 - d, y2));
                }
                if y2 >= d {
                    c.push((x1, y2 - d));
                }
                if y1 + d < w {
                    c.push((x2, y1 + d));
                }
                if x2 + d < h {
                    c.push((x2 + d, y1));
                }

                for (x3, y3) in c.into_iter() {
                    if board[x3][y3] {
                        ans -= 1;
                    }
                }
            }
        }
    }

    println!("{}", ans);
}

fn solve(board: &Vec<Vec<bool>>) -> usize {
    let h = board.len();
    let w = board[0].len();
    let mut map = BTreeMap::new();
    for x in 0..h {
        for y in 0..w {
            if board[x][y] {
                // y = -x + l
                let l = x + y;
                map.entry(l).or_insert(Vec::new()).push((x, y));
            }
        }
    }

    let sum: BTreeMap<usize, Vec<usize>> = map
        .iter()
        .map(|(&l, v)| {
            let mut board = vec![0; h];
            for &(x, _) in v.iter() {
                board[x] = 1;
            }
            let mut sum = vec![0; h + 1];
            for i in 0..h {
                sum[i + 1] = sum[i] + board[i];
            }
            (l, sum)
        })
        .collect();

    let mut ans = 0;
    for (&l, v) in map.iter() {
        for j in 0..v.len() {
            for i in 0..j {
                let (x1, y1) = v[i];
                let (x2, y2) = v[j];
                assert_eq!(x2 - x1, y1 - y2);
                let d = x2 - x1;

                if l >= 2 * d {
                    let lower = if x1 >= d { x1 - d } else { 0 };
                    let upper = x1 + 1;
                    let l3 = l - 2 * d;
                    if let Some(sum) = sum.get(&l3) {
                        ans += sum[upper] - sum[lower];
                    }
                }

                let lower = x2;
                let upper = cmp::min(x2 + d + 1, h);
                let l3 = l + 2 * d;
                if let Some(sum) = sum.get(&l3) {
                    ans += sum[upper] - sum[lower];
                }
            }
        }
    }
    ans
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .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()
    }
}

atcoder.jp

use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let mut edges = vec![];

    let mut left = 0;
    let mut right = 0;
    for i in 0..n {
        let a: u64 = sc.read();
        let b: u64 = sc.read();
        left += a;
        right += b;
        edges.push((a, i, true));
        edges.push((b, i, false));
    }
    edges.sort();

    let mut ans = cmp::min(left, right);

    let mut count = vec![0; n];
    let mut sum = 0;
    for i in 0..n {
        let (cost, i, _) = edges[i];
        count[i] += 1;
        sum += cost;
    }

    if count.iter().any(|&x| x != 1) {
        println!("{}", cmp::min(ans, sum));
        return;
    }

    if edges[n - 1].1 != edges[n].1 {
        sum -= edges[n - 1].0;
        sum += edges[n].0;
        println!("{}", cmp::min(ans, sum));
        return;
    }

    ans = cmp::min(ans, sum - edges[n - 2].0 + edges[n].0);
    ans = cmp::min(ans, sum - edges[n - 1].0 + edges[n + 1].0);
    println!("{}", ans);
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .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()
    }
}