#1107833 (Rust) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: 👑 terry_u16
• 提出日時: 2025-07-26 13:48:44
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 7 ms / 2,000 ms
• コード長: 18,155 bytes
• コンパイル時間: 14,793 ms
• コンパイル使用メモリ: 400,020 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,575,659,115
• 最終ジャッジ日時: 2025-07-26 13:49:33
• 合計ジャッジ時間: 14,660 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
other	AC * 50

ソースコード

#[allow(dead_code)]
mod grid {
    use std::{
        fmt::Display,
        ops::{Add, AddAssign, Index, IndexMut},
    };

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
    pub struct Coord {
        row: u8,
        col: u8,
    }

    impl Coord {
        pub const fn new(row: usize, col: usize) -> Self {
            Self {
                row: row as u8,
                col: col as u8,
            }
        }

        pub const fn row(&self) -> usize {
            self.row as usize
        }

        pub const fn col(&self) -> usize {
            self.col as usize
        }

        pub fn in_map(&self, size: usize) -> bool {
            self.row < size as u8 && self.col < size as u8
        }

        pub const fn to_index(&self, size: usize) -> CoordIndex {
            CoordIndex(self.row as usize * size + self.col as usize)
        }

        pub const fn dist(&self, other: &Self) -> usize {
            Self::dist_1d(self.row, other.row) + Self::dist_1d(self.col, other.col)
        }

        const fn dist_1d(x0: u8, x1: u8) -> usize {
            x0.abs_diff(x1) as usize
        }
    }

    impl Display for Coord {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "({}, {})", self.row, self.col)
        }
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
    pub struct CoordIndex(pub usize);

    impl CoordIndex {
        pub const fn to_coord(&self, size: usize) -> Coord {
            Coord::new(self.0 / size, self.0 % size)
        }
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
    pub struct CoordDiff {
        dr: i8,
        dc: i8,
    }

    impl CoordDiff {
        pub const fn new(dr: i32, dc: i32) -> Self {
            Self {
                dr: dr as i8,
                dc: dc as i8,
            }
        }

        pub const fn invert(&self) -> Self {
            Self {
                dr: -self.dr,
                dc: -self.dc,
            }
        }

        pub const fn dr(&self) -> i32 {
            self.dr as i32
        }

        pub const fn dc(&self) -> i32 {
            self.dc as i32
        }
    }

    impl Display for CoordDiff {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "({}, {})", self.dr, self.dc)
        }
    }

    impl Add<CoordDiff> for Coord {
        type Output = Coord;

        fn add(self, rhs: CoordDiff) -> Self::Output {
            Coord {
                row: self.row.wrapping_add(rhs.dr as u8),
                col: self.col.wrapping_add(rhs.dc as u8),
            }
        }
    }

    impl AddAssign<CoordDiff> for Coord {
        fn add_assign(&mut self, rhs: CoordDiff) {
            self.row = self.row.wrapping_add(rhs.dr as u8);
            self.col = self.col.wrapping_add(rhs.dc as u8);
        }
    }

    pub const ADJACENTS: [CoordDiff; 4] = [
        CoordDiff::new(-1, 0),
        CoordDiff::new(0, 1),
        CoordDiff::new(1, 0),
        CoordDiff::new(0, -1),
    ];

    pub const U: usize = 0;
    pub const R: usize = 1;
    pub const D: usize = 2;
    pub const L: usize = 3;
    pub const DIRECTIONS: [char; 4] = ['U', 'R', 'D', 'L'];

    #[derive(Debug, Clone)]
    pub struct Map2d<T> {
        size: usize,
        map: Vec<T>,
    }

    impl<T> Map2d<T> {
        pub fn new(map: Vec<T>, size: usize) -> Self {
            debug_assert!(size * size == map.len());
            Self { size, map }
        }

        pub fn from_fn(mut f: impl FnMut(Coord) -> T, size: usize) -> Self {
            let mut map = Vec::with_capacity(size * size);

            for row in 0..size {
                for col in 0..size {
                    map.push(f(Coord::new(row, col)));
                }
            }

            Self { size, map }
        }

        pub fn iter(&self) -> impl Iterator<Item = &T> {
            self.map.iter()
        }
    }

    impl<T: Default + Clone> Map2d<T> {
        pub fn with_default(size: usize) -> Self {
            let map = vec![T::default(); size * size];
            Self { size, map }
        }
    }

    impl<T> Index<Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coordinate: Coord) -> &Self::Output {
            &self.map[coordinate.to_index(self.size).0]
        }
    }

    impl<T> IndexMut<Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coordinate: Coord) -> &mut Self::Output {
            &mut self.map[coordinate.to_index(self.size).0]
        }
    }

    impl<T> Index<&Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coordinate: &Coord) -> &Self::Output {
            &self.map[coordinate.to_index(self.size).0]
        }
    }

    impl<T> IndexMut<&Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coordinate: &Coord) -> &mut Self::Output {
            &mut self.map[coordinate.to_index(self.size).0]
        }
    }

    impl<T> Index<usize> for Map2d<T> {
        type Output = [T];

        #[inline]
        fn index(&self, row: usize) -> &Self::Output {
            let begin = row * self.size;
            let end = begin + self.size;
            &self.map[begin..end]
        }
    }

    impl<T> IndexMut<usize> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, row: usize) -> &mut Self::Output {
            let begin = row * self.size;
            let end = begin + self.size;
            &mut self.map[begin..end]
        }
    }

    impl<T> Index<CoordIndex> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, index: CoordIndex) -> &Self::Output {
            &self.map[index.0]
        }
    }

    impl<T> IndexMut<CoordIndex> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, index: CoordIndex) -> &mut Self::Output {
            &mut self.map[index.0]
        }
    }

    #[derive(Debug, Clone)]
    pub struct ConstMap2d<T, const N: usize> {
        map: Vec<T>,
    }

    impl<T, const N: usize> ConstMap2d<T, N> {
        pub fn new(map: Vec<T>) -> Self {
            assert_eq!(map.len(), N * N);
            Self { map }
        }

        pub fn from_fn(mut f: impl FnMut(Coord) -> T) -> Self {
            let mut map = Vec::with_capacity(N * N);

            for row in 0..N {
                for col in 0..N {
                    map.push(f(Coord::new(row, col)));
                }
            }

            Self { map }
        }
    }

    impl<T: Default + Clone, const N: usize> ConstMap2d<T, N> {
        pub fn with_default() -> Self {
            let map = vec![T::default(); N * N];
            Self { map }
        }
    }

    impl<T, const N: usize> Index<Coord> for ConstMap2d<T, N> {
        type Output = T;

        #[inline]
        fn index(&self, coordinate: Coord) -> &Self::Output {
            &self.map[coordinate.to_index(N).0]
        }
    }

    impl<T, const N: usize> IndexMut<Coord> for ConstMap2d<T, N> {
        #[inline]
        fn index_mut(&mut self, coordinate: Coord) -> &mut Self::Output {
            &mut self.map[coordinate.to_index(N).0]
        }
    }

    impl<T, const N: usize> Index<&Coord> for ConstMap2d<T, N> {
        type Output = T;

        #[inline]
        fn index(&self, coordinate: &Coord) -> &Self::Output {
            &self.map[coordinate.to_index(N).0]
        }
    }

    impl<T, const N: usize> IndexMut<&Coord> for ConstMap2d<T, N> {
        #[inline]
        fn index_mut(&mut self, coordinate: &Coord) -> &mut Self::Output {
            &mut self.map[coordinate.to_index(N).0]
        }
    }

    impl<T, const N: usize> Index<usize> for ConstMap2d<T, N> {
        type Output = [T];

        #[inline]
        fn index(&self, row: usize) -> &Self::Output {
            let begin = row * N;
            let end = begin + N;
            &self.map[begin..end]
        }
    }

    impl<T, const N: usize> IndexMut<usize> for ConstMap2d<T, N> {
        #[inline]
        fn index_mut(&mut self, row: usize) -> &mut Self::Output {
            let begin = row * N;
            let end = begin + N;
            &mut self.map[begin..end]
        }
    }

    impl<T, const N: usize> Index<CoordIndex> for ConstMap2d<T, N> {
        type Output = T;

        #[inline]
        fn index(&self, index: CoordIndex) -> &Self::Output {
            &self.map[index.0]
        }
    }

    impl<T, const N: usize> IndexMut<CoordIndex> for ConstMap2d<T, N> {
        #[inline]
        fn index_mut(&mut self, index: CoordIndex) -> &mut Self::Output {
            &mut self.map[index.0]
        }
    }

    #[cfg(test)]
    mod test {
        use super::{ConstMap2d, Coord, CoordDiff, Map2d};

        #[test]
        fn coord_add() {
            let c = Coord::new(2, 4);
            let d = CoordDiff::new(-3, 5);
            let actual = c + d;

            let expected = Coord::new(!0, 9);
            assert_eq!(expected, actual);
        }

        #[test]
        fn coord_add_assign() {
            let mut c = Coord::new(2, 4);
            let d = CoordDiff::new(-3, 5);
            c += d;

            let expected = Coord::new(!0, 9);
            assert_eq!(expected, c);
        }

        #[test]
        fn map_new() {
            let map = Map2d::new(vec![0, 1, 2, 3], 2);
            let actual = map[Coord::new(1, 0)];
            let expected = 2;
            assert_eq!(expected, actual);
        }

        #[test]
        fn map_default() {
            let map = Map2d::with_default(2);
            let actual = map[Coord::new(1, 0)];
            let expected = 0;
            assert_eq!(expected, actual);
        }

        #[test]
        fn const_map_new() {
            let map = ConstMap2d::<_, 2>::new(vec![0, 1, 2, 3]);
            let actual = map[Coord::new(1, 0)];
            let expected = 2;
            assert_eq!(expected, actual);
        }

        #[test]
        fn const_map_default() {
            let map = ConstMap2d::<_, 2>::with_default();
            let actual = map[Coord::new(1, 0)];
            let expected = 0;
            assert_eq!(expected, actual);
        }
    }
}
mod problem {
    use std::fmt::Display;

    use crate::grid::Map2d;
    use proconio::input;

    #[derive(Debug, Clone)]
    pub struct Input {
        pub map: Map2d<u32>,
    }

    impl Input {
        pub const MAP_SIZE: usize = 10;
        pub const MAX_TURN: usize = 1000;

        pub fn read() -> Self {
            input! {
                n: usize,
                t: usize,
                map: [u32; n * n]
            }

            assert_eq!(n, Self::MAP_SIZE);
            assert_eq!(t, Self::MAX_TURN);
            let map = Map2d::new(map, Self::MAP_SIZE);

            Self { map }
        }
    }

    #[derive(Debug, Clone)]
    pub struct Output(pub Vec<Action>);

    impl Display for Output {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            for action in &self.0 {
                writeln!(f, "{}", action)?;
            }

            Ok(())
        }
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
    pub enum Action {
        Up,
        Right,
        Down,
        Left,
        Write,
        Copy,
    }

    impl Display for Action {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            match self {
                Action::Up => write!(f, "U"),
                Action::Right => write!(f, "R"),
                Action::Down => write!(f, "D"),
                Action::Left => write!(f, "L"),
                Action::Write => write!(f, "W"),
                Action::Copy => write!(f, "C"),
            }
        }
    }
}
mod solver {
    use std::usize;

    use crate::{
        grid::{Coord, Map2d, ADJACENTS, D, L, R, U},
        problem::{Action, Input, Output},
        util::ChangeMinMax,
    };

    pub(super) fn solve(input: &Input) -> Output {
        let mut state = State::new(input);

        for target_digit in (0..20).rev() {
            eprintln!("target_digit: {}", target_digit);
            eprintln!("{:0>20b}", state.s);
            state.print_map();

            match process_digit(&mut state, target_digit) {
                Ok(()) => {}
                Err(()) => break,
            }
        }

        eprintln!("turn: {}", state.turn);
        eprintln!("score: {}", state.score);

        Output(state.actions)
    }

    fn process_digit(state: &mut State, target_digit: u32) -> Result<(), ()> {
        let mut best_position = None;
        let mut best_dist = usize::MAX;

        for row in 0..Input::MAP_SIZE {
            for col in 0..Input::MAP_SIZE {
                let c = Coord::new(row, col);
                let xor = state.s ^ state.map[c];
                let masked = xor & (!0 << target_digit);

                if masked == (1 << target_digit) && best_dist.change_min(c.dist(&state.position)) {
                    best_position = Some(c);
                }
            }
        }

        let Some(target) = best_position else {
            // 見つからないパターン
            eprintln!("No target found for digit {}", target_digit);
            return Ok(());
        };

        state.move_to(target)?;
        state.apply(Action::Copy)?;
        state.move_to(Coord::new(0, 0))?;

        for row in 0..Input::MAP_SIZE {
            if row % 2 == 0 {
                state.write_if_improve()?;

                for _ in 1..Input::MAP_SIZE {
                    state.apply(Action::Right)?;
                    state.write_if_improve()?;
                }
            } else {
                state.write_if_improve()?;

                for _ in (0..Input::MAP_SIZE - 1).rev() {
                    state.apply(Action::Left)?;
                    state.write_if_improve()?;
                }
            }

            if row < Input::MAP_SIZE - 1 {
                state.apply(Action::Down)?;
            }
        }

        Ok(())
    }

    #[derive(Debug, Clone)]
    struct State {
        map: Map2d<u32>,
        score: u32,
        s: u32,
        turn: usize,
        position: Coord,
        actions: Vec<Action>,
    }

    impl State {
        fn new(input: &Input) -> Self {
            let map = input.map.clone();
            let position = Coord::new(0, 0);
            let score = map.iter().sum();

            Self {
                map,
                score,
                s: 0,
                turn: 0,
                position,
                actions: vec![],
            }
        }

        fn apply(&mut self, action: Action) -> Result<(), ()> {
            if self.turn >= Input::MAX_TURN {
                return Err(());
            }

            self.turn += 1;
            self.actions.push(action);

            match action {
                Action::Up => self.position += ADJACENTS[U],
                Action::Right => self.position += ADJACENTS[R],
                Action::Down => self.position += ADJACENTS[D],
                Action::Left => self.position += ADJACENTS[L],
                Action::Write => {
                    self.score -= self.map[self.position];
                    self.map[self.position] ^= self.s;
                    self.score += self.map[self.position];
                }
                Action::Copy => self.s ^= self.map[self.position],
            }

            Ok(())
        }

        fn move_to(&mut self, target: Coord) -> Result<(), ()> {
            let mut actions = vec![];

            while self.position.row() > target.row() {
                actions.push(Action::Up);
                self.apply(Action::Up)?;
            }

            while self.position.col() < target.col() {
                actions.push(Action::Right);
                self.apply(Action::Right)?;
            }

            while self.position.row() < target.row() {
                actions.push(Action::Down);
                self.apply(Action::Down)?;
            }

            while self.position.col() > target.col() {
                actions.push(Action::Left);
                self.apply(Action::Left)?;
            }

            Ok(())
        }

        fn write_if_improve(&mut self) -> Result<(), ()> {
            let v = self.map[self.position];

            if v < v ^ self.s {
                self.apply(Action::Write)?;
            }

            Ok(())
        }

        fn print_map(&self) {
            for row in 0..Input::MAP_SIZE {
                for col in 0..Input::MAP_SIZE {
                    eprint!("{:0>20b} ", self.map[Coord::new(row, col)]);
                }

                eprintln!();
            }
        }
    }
}
#[allow(dead_code)]
mod util {
    //! よく使われるユーティリティ関数をまとめたモジュール

    /// 最小値と最大値を更新するトレイト
    ///
    /// # Examples
    ///
    /// ```
    /// use cp_lib_rs::util::ChangeMinMax;
    ///
    /// let mut x = 10;
    /// assert!(x.change_min(3));
    /// assert_eq!(x, 3);
    /// ```
    #[allow(dead_code)]
    pub trait ChangeMinMax {
        fn change_min(&mut self, v: Self) -> bool;
        fn change_max(&mut self, v: Self) -> bool;
    }

    impl<T: PartialOrd> ChangeMinMax for T {
        fn change_min(&mut self, v: T) -> bool {
            *self > v && {
                *self = v;
                true
            }
        }

        fn change_max(&mut self, v: T) -> bool {
            *self < v && {
                *self = v;
                true
            }
        }
    }

    /// 多次元配列を作成する
    ///
    /// # Examples
    ///
    /// ```
    /// use cp_lib_rs::mat;
    ///
    /// let a = mat![0; 4; 3];
    /// assert_eq!(a, vec![vec![0; 3]; 4]);
    /// ```
    #[macro_export]
    macro_rules! mat {
	($($e:expr),*) => { vec![$($e),*] };
	($($e:expr,)*) => { vec![$($e),*] };
	($e:expr; $d:expr) => { vec![$e; $d] };
	($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}
}

fn main() {
    let input = problem::Input::read();
    let output = solver::solve(&input);
    println!("{}", output);
}