結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
👑  terry_u16
|
| 提出日時 | 2025-07-26 14:22:40 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 19,836 bytes |
| コンパイル時間 | 14,487 ms |
| コンパイル使用メモリ | 403,384 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 5,109,687,900 |
| 最終ジャッジ日時 | 2025-07-26 14:22:57 |
| 合計ジャッジ時間 | 16,590 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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);
let targets = (0..Input::MAP_SIZE)
.map(|col| Coord::new(0, col))
.collect::<Vec<_>>();
create_base(&mut state, &targets).unwrap();
for target_digit in (0..20).rev() {
if state.turn >= 800 {
break;
}
eprintln!("target_digit: {}", target_digit);
eprintln!("{:0>20b}", state.s);
state.print_map();
match process_digit(&mut state, target_digit) {
Ok(()) => {}
Err(()) => break,
}
}
clean_up(&mut state, &targets).unwrap();
eprintln!("turn: {}", state.turn);
eprintln!("score: {}", state.score);
Output(state.actions)
}
fn create_base(state: &mut State, targets: &[Coord]) -> Result<(), ()> {
for i in 1..targets.len() {
state.move_to(targets[i])?;
state.apply(Action::Copy)?;
state.apply(Action::Write)?;
for j in 0..i {
if state.s > state.s ^ state.map[targets[j]] {
state.move_to(targets[j])?;
state.apply(Action::Copy)?;
}
}
state.move_to(targets[i])?;
state.apply(Action::Write)?;
state.apply(Action::Copy)?;
}
Ok(())
}
fn process_digit(state: &mut State, target_digit: u32) -> Result<(), ()> {
let mut best_position = None;
let mut best_dist = usize::MAX;
for col in 0..Input::MAP_SIZE {
let c = Coord::new(0, 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(base) = best_position else {
// 見つからないパターン
eprintln!("No target found for digit {}", target_digit);
return Ok(());
};
state.move_to(base)?;
state.apply(Action::Copy)?;
state.move_to(Coord::new(1, 0))?;
for row in 1..Input::MAP_SIZE {
if row % 2 == 1 {
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)?;
}
}
state.move_to(base)?;
state.apply(Action::Copy)?;
Ok(())
}
fn clean_up(state: &mut State, targets: &[Coord]) -> Result<(), ()> {
let mut best_position = Coord::new(0, 0);
let mut max = 0;
for row in 0..Input::MAP_SIZE {
for col in 0..Input::MAP_SIZE {
let c = Coord::new(row, col);
if targets.contains(&c) {
continue;
}
if max.change_max(state.map[c]) {
best_position = c;
}
}
}
state.move_to(best_position)?;
state.apply(Action::Copy)?;
for &c in targets.iter() {
if state.map[c] < state.map[c] ^ state.s {
state.move_to(c)?;
state.apply(Action::Write)?;
}
}
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);
}