結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 terry_u16
|
| 提出日時 | 2022-06-12 15:38:48 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 885 ms / 2,000 ms |
| コード長 | 10,028 bytes |
| コンパイル時間 | 1,306 ms |
| 実行使用メモリ | 22,864 KB |
| スコア | 65,313 |
| 平均クエリ数 | 347.87 |
| 最終ジャッジ日時 | 2022-06-12 15:39:39 |
| 合計ジャッジ時間 | 36,683 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
コンパイルメッセージ
warning: constant is never used: `MAX_MOVES` --> Main.rs:98:1 | 98 | const MAX_MOVES: usize = 400; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: 1 warning emitted
ソースコード
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::<Vec<_>>()};($($t:ty),*; $n:expr) => {(0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()};($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::<Vec<_>>()}};($t:ty ;; $n:expr) => {(0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()};}const MAP_SIZE: usize = 20;const MAX_MOVES: usize = 400;const DEFAULT_PROB: f64 = 1.0 - 0.25;#[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<Coordinate>,state: EdgeState,}impl Edge {fn new(next: Option<Coordinate>, state: EdgeState) -> Self {Self { next, state }}}#[derive(Debug, Clone, Copy)]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,EdgeState::MayBeWall(c) => p.powi(*c),}}}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 {for trial in 0.. {let moves = dp(input, &state);if let Some(stop) = write_output(&moves) {update_state(&mut state, &moves[..stop], moves[stop])} else {return 1001 - trial - 1;}}0}fn dp(input: &Input, state: &State) -> Vec<usize> {const MAX_MOVES: usize = 100;let mut dp = vec![Map2d::new(vec![0.0; MAP_SIZE * MAP_SIZE], MAP_SIZE); MAX_MOVES + 1];let mut from = vec![Map2d::new(vec![0; MAP_SIZE * MAP_SIZE], MAP_SIZE); MAX_MOVES + 1];dp[0][Coordinate::new(0, 0)] = 1.0;for turn in 0..MAX_MOVES {for row in 0..MAP_SIZE {for col in 0..MAP_SIZE {let c = Coordinate::new(row, col);for dir in 0..4 {let edge = state.map[c][dir];if let Some(next) = edge.next {let prob = edge.state.prob(input.p);if chmax!(dp[turn + 1][next], dp[turn][c] * prob) {from[turn + 1][next] = dir;}}}}}}let mut max_prob = 0.0;let mut max_turn = 0;let goal = Coordinate::new(MAP_SIZE - 1, MAP_SIZE - 1);for turn in 0..=MAX_MOVES {if chmax!(max_prob, dp[turn][goal]) {max_turn = turn;}}let mut current = goal;let mut turn = max_turn;let mut moves = vec![];while turn > 0 {let dir = from[turn][current];moves.push(dir);current = current + ADJACENTS[dir ^ 2];turn -= 1;}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 write_output(moves: &[usize]) -> Option<usize> {let output = moves.iter().map(|dir| DIRECTIONS[*dir]).collect::<String>();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<CoordinateDiff> 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<T> {pub width: usize,pub height: usize,map: Vec<T>,}impl<T> Map2d<T> {pub fn new(map: Vec<T>, width: usize) -> Self {let height = map.len() / width;debug_assert!(width * height == map.len());Self { width, height, map }}}impl<T> std::ops::Index<Coordinate> for Map2d<T> {type Output = T;#[inline]fn index(&self, coordinate: Coordinate) -> &Self::Output {&self.map[coordinate.row * self.width + coordinate.col]}}impl<T> std::ops::IndexMut<Coordinate> for Map2d<T> {#[inline]fn index_mut(&mut self, coordinate: Coordinate) -> &mut Self::Output {&mut self.map[coordinate.row * self.width + coordinate.col]}}impl<T> std::ops::Index<&Coordinate> for Map2d<T> {type Output = T;#[inline]fn index(&self, coordinate: &Coordinate) -> &Self::Output {&self.map[coordinate.row * self.width + coordinate.col]}}impl<T> std::ops::IndexMut<&Coordinate> for Map2d<T> {#[inline]fn index_mut(&mut self, coordinate: &Coordinate) -> &mut Self::Output {&mut self.map[coordinate.row * self.width + coordinate.col]}}impl<T> std::ops::Index<usize> for Map2d<T> {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<T> std::ops::IndexMut<usize> for Map2d<T> {#[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]}}}