use std::collections::BinaryHeap; use grid::{Coordinate, Map2d, ADJACENTS, DIRECTIONS}; #[allow(unused_macros)] macro_rules! chmin { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_min = min!($($cmps),+); if $base > cmp_min { $base = cmp_min; true } else { false } }}; } #[allow(unused_macros)] macro_rules! chmax { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_max = max!($($cmps),+); if $base < cmp_max { $base = cmp_max; true } else { false } }}; } #[allow(unused_macros)] macro_rules! min { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::min($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::min($a, min!($($rest),+)) }}; } #[allow(unused_macros)] macro_rules! max { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::max($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::max($a, max!($($rest),+)) }}; } macro_rules! get { ($t:ty) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().parse::<$t>().unwrap() } }; ($($t:ty),*) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( $(iter.next().unwrap().parse::<$t>().unwrap(),)* ) } }; ($t:ty; $n:expr) => { (0..$n).map(|_| get!($t) ).collect::>() }; ($($t:ty),*; $n:expr) => { (0..$n).map(|_| get!($($t),*) ).collect::>() }; ($t:ty ;;) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse::<$t>().unwrap()) .collect::>() } }; ($t:ty ;; $n:expr) => { (0..$n).map(|_| get!($t ;;)).collect::>() }; } const MAP_SIZE: usize = 20; const DEFAULT_PROB: f64 = 1.0 - 0.2; #[derive(Debug, Clone, Copy)] struct Input { p: f64, } #[derive(Debug, Clone)] struct State { map: Map2d<[Edge; 4]>, } #[derive(Debug, Clone, Copy)] struct Edge { next: Option, state: EdgeState, } impl Edge { fn new(next: Option, state: EdgeState) -> Self { Self { next, state } } } #[derive(Debug, Clone, Copy, PartialEq, Eq)] enum EdgeState { NotEnter, NoWall, MayBeWall(i32), } impl EdgeState { #[inline] fn prob(&self, p: f64) -> f64 { match self { EdgeState::NotEnter => DEFAULT_PROB, EdgeState::NoWall => 1.0 - p, EdgeState::MayBeWall(c) => p.powi(*c), } } } // Partial orderなものをTotal orderにする #[derive(PartialEq, PartialOrd)] pub struct Total(pub T); impl Eq for Total {} impl Ord for Total { fn cmp(&self, other: &Total) -> std::cmp::Ordering { self.0.partial_cmp(&other.0).unwrap() } } fn main() { let (input, state) = read_input(); let score = solve(&input, state); eprintln!("score: {}", score); } fn read_input() -> (Input, State) { let (_, _, p) = get!(usize, usize, i64); let p = p as f64 * 0.01; let mut map = Map2d::new( vec![[Edge::new(None, EdgeState::NotEnter); 4]; MAP_SIZE * MAP_SIZE], MAP_SIZE, ); for row in 0..MAP_SIZE { for col in 0..MAP_SIZE { let c = Coordinate::new(row, col); for (dir, adj) in ADJACENTS.iter().enumerate() { let next = c + *adj; if next.in_map(MAP_SIZE) { map[c][dir].next = Some(next); } } } } let input = Input { p }; let state = State { map }; (input, state) } fn solve(input: &Input, mut state: State) -> i64 { let mut rng = Xorshift::new(); for trial in 0.. { let moves = dijkstra(input, &state); let moves = mod_moves(moves, &state, &mut rng); if let Some(stop) = write_output(&moves) { update_state(&mut state, &moves[..stop], moves[stop]) } else { return 1001 - trial - 1; } } 0 } fn dijkstra(input: &Input, state: &State) -> Vec { let mut distances = Map2d::new(vec![0.0; MAP_SIZE * MAP_SIZE], MAP_SIZE); let mut from = Map2d::new(vec![0; MAP_SIZE * MAP_SIZE], MAP_SIZE); let mut queue = BinaryHeap::new(); distances[Coordinate::new(0, 0)] = 1.0; queue.push((Total(1.0), Coordinate::new(0, 0))); let goal = Coordinate::new(MAP_SIZE - 1, MAP_SIZE - 1); while let Some((Total(p), c)) = queue.pop() { if distances[c] < p { continue; } if c == goal { break; } for dir in 0..4 { let edge = state.map[c][dir]; if let Some(next) = edge.next { let prob = (edge.state.prob(input.p) - 5e-3 * (c.row as f64 - c.col as f64).abs()) .max(0.0); let next_p = p * prob; if chmax!(distances[next], next_p) { from[next] = dir; queue.push((Total(next_p), next)); } } } } let mut current = goal; let mut moves = vec![]; while current != Coordinate::new(0, 0) { let dir = from[current]; moves.push(dir); current = current + ADJACENTS[dir ^ 2]; } moves.reverse(); moves } fn update_state(state: &mut State, ok: &[usize], ng: usize) { let mut current = Coordinate::new(0, 0); for &ok in ok { state.map[current][ok].state = EdgeState::NoWall; current = current + ADJACENTS[ok]; } state.map[current][ng].state = match state.map[current][ng].state { EdgeState::NotEnter => EdgeState::MayBeWall(1), EdgeState::NoWall => EdgeState::NoWall, EdgeState::MayBeWall(c) => EdgeState::MayBeWall(c + 1), } } fn mod_moves(mut moves: Vec, state: &State, rng: &mut Xorshift) -> Vec { let mut last_seen = 0; let mut current = Coordinate::new(0, 0); for (i, m) in moves.iter().enumerate() { let adj = ADJACENTS[*m]; let s = state.map[current][*m].state; if s != EdgeState::NotEnter { last_seen = i; } current = current + adj; } loop { for i in (last_seen + 1)..moves.len() { let j = rng.rand((moves.len() - i) as u64) as usize + i; moves.swap(i, j); } let mut current = Coordinate::new(0, 0); let mut ok = true; for m in moves.iter() { let next = current + ADJACENTS[*m]; if !next.in_map(MAP_SIZE) { ok = false; break; } current = next; } if ok { break; } } moves } fn write_output(moves: &[usize]) -> Option { let output = moves.iter().map(|dir| DIRECTIONS[*dir]).collect::(); println!("{}", output); let judge = get!(i64); if judge == -1 { None } else { Some(judge as usize) } } #[allow(dead_code)] mod grid { #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Coordinate { pub row: usize, pub col: usize, } impl Coordinate { pub const fn new(row: usize, col: usize) -> Self { Self { row, col } } pub fn in_map(&self, size: usize) -> bool { self.row < size && self.col < size } pub const fn to_index(&self, size: usize) -> usize { self.row * size + self.col } 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: usize, x1: usize) -> usize { (x0 as i64 - x1 as i64).abs() as usize } } #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct CoordinateDiff { pub dr: usize, pub dc: usize, } impl CoordinateDiff { pub const fn new(dr: usize, dc: usize) -> Self { Self { dr, dc } } pub const fn invert(&self) -> Self { Self::new(0usize.wrapping_sub(self.dr), 0usize.wrapping_sub(self.dc)) } } impl std::ops::Add for Coordinate { type Output = Coordinate; fn add(self, rhs: CoordinateDiff) -> Self::Output { Coordinate::new(self.row.wrapping_add(rhs.dr), self.col.wrapping_add(rhs.dc)) } } pub const ADJACENTS: [CoordinateDiff; 4] = [ CoordinateDiff::new(!0, 0), CoordinateDiff::new(0, 1), CoordinateDiff::new(1, 0), CoordinateDiff::new(0, !0), ]; pub const DIRECTIONS: [char; 4] = ['U', 'R', 'D', 'L']; #[derive(Debug, Clone)] pub struct Map2d { pub width: usize, pub height: usize, map: Vec, } impl Map2d { pub fn new(map: Vec, width: usize) -> Self { let height = map.len() / width; debug_assert!(width * height == map.len()); Self { width, height, map } } } impl std::ops::Index for Map2d { type Output = T; #[inline] fn index(&self, coordinate: Coordinate) -> &Self::Output { &self.map[coordinate.row * self.width + coordinate.col] } } impl std::ops::IndexMut for Map2d { #[inline] fn index_mut(&mut self, coordinate: Coordinate) -> &mut Self::Output { &mut self.map[coordinate.row * self.width + coordinate.col] } } impl std::ops::Index<&Coordinate> for Map2d { type Output = T; #[inline] fn index(&self, coordinate: &Coordinate) -> &Self::Output { &self.map[coordinate.row * self.width + coordinate.col] } } impl std::ops::IndexMut<&Coordinate> for Map2d { #[inline] fn index_mut(&mut self, coordinate: &Coordinate) -> &mut Self::Output { &mut self.map[coordinate.row * self.width + coordinate.col] } } impl std::ops::Index for Map2d { type Output = [T]; #[inline] fn index(&self, row: usize) -> &Self::Output { let begin = row * self.width; let end = begin + self.width; &self.map[begin..end] } } impl std::ops::IndexMut for Map2d { #[inline] fn index_mut(&mut self, row: usize) -> &mut Self::Output { let begin = row * self.width; let end = begin + self.width; &mut self.map[begin..end] } } } #[derive(Debug)] #[allow(dead_code)] pub struct Xorshift { seed: u64, } impl Xorshift { #[allow(dead_code)] pub fn new() -> Xorshift { Xorshift { seed: 0xf0fb588ca2196dac, } } #[allow(dead_code)] pub fn with_seed(seed: u64) -> Xorshift { Xorshift { seed: seed } } #[inline] #[allow(dead_code)] pub fn next(&mut self) -> u64 { self.seed = self.seed ^ (self.seed << 13); self.seed = self.seed ^ (self.seed >> 7); self.seed = self.seed ^ (self.seed << 17); self.seed } #[inline] #[allow(dead_code)] pub fn rand(&mut self, m: u64) -> u64 { self.next() % m } #[inline] #[allow(dead_code)] // 0.0 ~ 1.0 pub fn randf(&mut self) -> f64 { use std::mem; const UPPER_MASK: u64 = 0x3FF0000000000000; const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF; let tmp = UPPER_MASK | (self.next() & LOWER_MASK); let result: f64 = unsafe { mem::transmute(tmp) }; result - 1.0 } }