結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
![]() |
提出日時 | 2023-05-07 10:38:53 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 41,746 bytes |
コンパイル時間 | 5,247 ms |
コンパイル使用メモリ | 184,712 KB |
実行使用メモリ | 5,248 KB |
スコア | 81,280 |
最終ジャッジ日時 | 2023-05-07 10:39:43 |
合計ジャッジ時間 | 44,948 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 98 WA * 2 |
ソースコード
#![allow(non_snake_case, unused)]use std::io::*;use std::{collections::*, fmt::format};use std::{cmp::*, vec};use crate::input::{*, marker::*};use crate::rand::Xoshiro256;const N: usize = 60;const H: i64 = 1500;const INF: i64 = 1_000_000_000;const TL: f64 = 2.9;const DIJ: [(usize, usize); 4] = [(!0, 0), (1, 0), (0, !0), (0, 1)];const DIR: [char; 4] = ['U', 'D', 'L', 'R'];// Actionは,(行動の種類, 方向)で持つtype Action = (char, usize);pub fn get_time() -> f64 {static mut STIME: f64 = -1.0;let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;unsafe {if STIME < 0.0 {STIME = ms;}// ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利#[cfg(feature = "local")]{(ms - STIME) * 1.5}#[cfg(not(feature = "local"))]{(ms - STIME)}}}// コピペで使える proconio もどき// cunitacさんからお借りしています// https://gist.github.com/cunitac/b00be62bf68c9fb6055d22eb77c17e14pub mod input {use std::{cell::RefCell,fmt::Debug,io::{stdin, BufRead, BufReader, Stdin},str::{FromStr, SplitWhitespace},};thread_local!(pub static STDIN_SOURCE: RefCell<Source> = RefCell::new(Source {stdin: BufReader::new(stdin()),tokens: "".split_whitespace(),}););pub struct Source {stdin: BufReader<Stdin>,tokens: SplitWhitespace<'static>,}impl Source {pub fn next_token(&mut self) -> Option<&str> {self.tokens.next().or_else(|| {let mut input = String::new();self.stdin.read_line(&mut input).unwrap();self.tokens = Box::leak(input.into_boxed_str()).split_whitespace();self.tokens.next()})}}#[macro_export]macro_rules! read_value {(from $s:expr, [$t:tt; $n:expr]) => {(0..$n).map(|_| $crate::read_value!(from $s, $t)).collect::<Vec<_>>()};(from $s:expr, [$t:tt]) => {let n = $crate::read_value!(from $s, usize);$crate::read_value!(from $s, [$t; n])};(from $s:expr, $t:ty) => {<$t as $crate::input::Readable>::read(&mut $s)};(from $s:expr, $($t:tt),* $(,)?) => {($($crate::read_value!(from $s, $t)),*)};($($r:tt)*) => {$crate::input::STDIN_SOURCE.with(|s| {let mut s = s.borrow_mut();$crate::read_value!(from s, $($r)*)})}}#[macro_export]macro_rules! input {() => {};($x:tt: $t:tt, $($r:tt)*) => {let $x = $crate::read_value!($t);$crate::input!($($r)*);};(mut $x:tt: $t:tt, $($r:tt)*) => {let mut $x = $crate::read_value!($t);$crate::input!($($r)*);};(from $s:expr, $x:tt, $t:tt, $($r:tt)*) => {let $x = $crate::read_value!(from $s, $t);$crate::input!(from $s, $($r)*);};(from $s:expr, mut $x:tt, $t:tt, $($r:tt)*) => {let mut $x = $crate::read_value!(from $s, $t);$crate::input!(from $s, $($r)*);};($($r:tt)*) => {$crate::input!($($r)*,);};}pub trait Readable {type Output;fn read(source: &mut Source) -> Self::Output;}impl<T: FromStr<Err = E>, E: Debug> Readable for T {type Output = T;fn read(source: &mut Source) -> T {source.next_token().unwrap().parse().unwrap()}}pub mod marker {macro_rules! impl_readable {($e:ident, $t:ty, $u:ty, $f:expr) => {pub enum $e {}impl $crate::input::Readable for $e {type Output = $t;fn read(mut source: &mut $crate::input::Source) -> $t {$f($crate::read_value!(from source, $u))}}};}impl_readable!(Usize1, usize, usize, |x| x - 1);impl_readable!(Isize1, isize, isize, |x| x - 1);impl_readable!(Chars, Vec<char>, String, |x: String| x.chars().collect());impl_readable!(Bytes, Vec<u8>, String, |x: String| x.bytes().collect());}}mod rand {pub(crate) struct Xoshiro256 {s0: u128,s1: u128,s2: u128,s3: u128,}impl Xoshiro256 {pub(crate) fn new(mut seed: u128) -> Self {let s0 = split_mix_128(&mut seed);let s1 = split_mix_128(&mut seed);let s2 = split_mix_128(&mut seed);let s3 = split_mix_128(&mut seed);Self { s0, s1, s2, s3 }}fn next(&mut self) -> u128 {let result = (self.s1.wrapping_mul(5)).rotate_left(7).wrapping_mul(9);let t = self.s1 << 17;self.s2 ^= self.s0;self.s3 ^= self.s1;self.s1 ^= self.s2;self.s0 ^= self.s3;self.s2 ^= t;self.s3 = self.s3.rotate_left(45);result}pub(crate) fn gen_usize(&mut self, lower: usize, upper: usize) -> usize {assert!(lower < upper);let count = upper - lower;(self.next() % count as u128) as usize + lower}pub(crate) fn gen_i64(&mut self, lower: i64, upper: i64) -> i64 {assert!(lower < upper);let count = upper - lower;(self.next() % count as u128) as i64 + lower}pub(crate) fn gen_u128(&mut self, lower: u128, upper: u128) -> u128 {assert!(lower < upper);let count = upper - lower;(self.next() % count as u128) as u128 + lower}pub(crate) fn gen_f64(&mut self) -> f64 {const UPPER_MASK: u128 = 0x3ff0000000000000;const LOWER_MASK: u128 = 0xfffffffffffff;let result = (UPPER_MASK | (self.next() & LOWER_MASK)) as u64;let result: f64 = unsafe { std::mem::transmute(result) };result - 1.0}pub(crate) fn gen_bool(&mut self, prob: f64) -> bool {self.gen_f64() < prob}}fn split_mix_128(x: &mut u128) -> u128 {*x = x.wrapping_add(0x9e3779b97f4a7c15);let mut z = *x;z = (z ^ z >> 30).wrapping_mul(0xbf58476d1ce4e5b9);z = (z ^ z >> 27).wrapping_mul(0x94d049bb133111eb);z ^ z >> 31}}const TRUE: &'static bool = &true;const FALSE: &'static bool = &false;#[derive(Clone, Debug)]/// Efficient bool collectionpub struct BitSet {buf: Vec<u64>,size: usize,}impl BitSet {#[allow(dead_code)]pub fn new(size: usize) -> BitSet {BitSet {buf: vec![0; (size + 63) / 64],size: size,}}#[allow(dead_code)]pub fn set(&mut self, i: usize, b: bool) {assert!(i < self.size);if b {self.buf[i >> 6] |= 1 << (i & 63);} else {self.buf[i >> 6] &= !(1 << (i & 63));}}#[allow(dead_code)]pub fn count_ones(&self) -> usize {let sum: u32 = self.buf.iter().map(|x| x.count_ones()).sum();sum as usize}#[allow(dead_code)]fn chomp(&mut self) {let r = self.size & 63;if r != 0 {if let Some(x) = self.buf.last_mut() {let d = 64 - r;*x = (*x << d) >> d;}}}}impl std::ops::Index<usize> for BitSet {type Output = bool;fn index(&self, index: usize) -> &bool {[FALSE, TRUE][(self.buf[index >> 6] >> (index & 63)) as usize & 1]}}impl std::ops::ShlAssign<usize> for BitSet {fn shl_assign(&mut self, x: usize) {let q = x >> 6;let r = x & 63;if q >= self.buf.len() {for x in &mut self.buf {*x = 0;}return;}if r == 0 {for i in (q..self.buf.len()).rev() {self.buf[i] = self.buf[i - q];}} else {for i in (q + 1..self.buf.len()).rev() {self.buf[i] = (self.buf[i - q] << r) | (self.buf[i - q - 1] >> (64 - r));}self.buf[q] = self.buf[0] << r;}for x in &mut self.buf[..q] {*x = 0;}self.chomp();}}impl std::ops::Shl<usize> for BitSet {type Output = Self;fn shl(mut self, x: usize) -> Self {self <<= x;self}}impl std::ops::ShrAssign<usize> for BitSet {fn shr_assign(&mut self, x: usize) {let q = x >> 6;let r = x & 63;if q >= self.buf.len() {for x in &mut self.buf {*x = 0;}return;}if r == 0 {for i in 0..self.buf.len() - q {self.buf[i] = self.buf[i + q];}} else {for i in 0..self.buf.len() - q - 1 {self.buf[i] = (self.buf[i + q] >> r) | (self.buf[i + q + 1] << (64 - r));}let len = self.buf.len();self.buf[len - q - 1] = self.buf[len - 1] >> r;}let len = self.buf.len();for x in &mut self.buf[len - q..] {*x = 0;}}}impl std::ops::Shr<usize> for BitSet {type Output = Self;fn shr(mut self, x: usize) -> Self {self >>= x;self}}impl<'a> std::ops::BitAndAssign<&'a BitSet> for BitSet {fn bitand_assign(&mut self, rhs: &'a Self) {for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {*a &= *b;}}}impl<'a> std::ops::BitAnd<&'a BitSet> for BitSet {type Output = Self;fn bitand(mut self, rhs: &'a Self) -> Self {self &= rhs;self}}impl<'a> std::ops::BitOrAssign<&'a BitSet> for BitSet {fn bitor_assign(&mut self, rhs: &'a Self) {for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {*a |= *b;}self.chomp();}}impl<'a> std::ops::BitOr<&'a BitSet> for BitSet {type Output = Self;fn bitor(mut self, rhs: &'a Self) -> Self {self |= rhs;self}}impl<'a> std::ops::BitXorAssign<&'a BitSet> for BitSet {fn bitxor_assign(&mut self, rhs: &'a Self) {for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {*a ^= *b;}self.chomp();}}impl<'a> std::ops::BitXor<&'a BitSet> for BitSet {type Output = Self;fn bitxor(mut self, rhs: &'a Self) -> Self {self ^= rhs;self}}#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]pub struct Position {y: i64,x: i64,}impl Position {fn new(y: i64, x: i64) -> Self {Self { y, x }}}#[derive(Clone)]struct Map {N: usize,D: i64,H: i64,S: Vec<Vec<char>>,M: usize,key: (usize, usize),goal: (usize, usize),jewelry: Vec<(usize, usize)>,gunpowder: Vec<(usize, usize)>,wall: Vec<bool>,interval_of_probe: Vec<i64>,}impl Map {fn new() -> Self {// 標準入力を受け取るinput! {_N: usize,D: i64,_H: i64,}let mut S = vec![];for _ in 0..N {input! {Si: Chars,}S.push(Si);}// 鍵,ゴール,宝石,火薬,壁位置を発見しておくlet mut key = (!0, !0);let mut goal = (!0, !0);let mut jewelry = vec![];let mut gunpowder = vec![];let mut wall = vec![false; N*N];for y in 0..N {for x in 0..N {if S[y][x] == '#' {wall[y * N + x] = true;} else if S[y][x] == 'K' {key = (y, x);} else if S[y][x] == 'G' {goal = (y, x);} else if S[y][x] == 'J' {jewelry.push((y, x));} else if S[y][x] == 'F' {gunpowder.push((y, x));}}}input! {M: usize,}let mut interval_of_probe = vec![0; N*N];for _ in 0..M {input! {y: usize,x: usize,di: i64,}interval_of_probe[y * N + x] = di;}Self { N, D, H, S, M, key, goal, jewelry, gunpowder, wall, interval_of_probe }}}// 時刻tにおける盤面の状態を保持する構造体#[derive(Clone)]struct State<'a> {turn: i64,is_done: bool,evaluated_score: i64, // 評価関数値jewelry_map: BitSet, // 宝石位置を表すbitsetgunpowder_map: BitSet, // 火薬位置を表すbitsetblock_map: BitSet, // ブロック位置を表すbitsetprobe_map: BitSet, // 探知機位置を表すbitsetpos: (usize, usize), // プレイヤーの現在地の(y, x)hp: i64, // プレイヤーの体力jewelry: i64, // 宝石の数 (これx10が実際のゲームスコア)gunpowder: i64, // 火薬の数has_key: bool, // 鍵を持っているかどうかoutput: Vec<(char, char)>, // 出力zobrist_hash: u128, // 各マップの状態をなるべく一意に定めるzobrist hash値zobrist_hash_map: &'a ZobristHash, // ある座標にプレイヤー・コインがあることを示すハッシュ値を持つ}impl<'a> State<'a> {fn new(map: &Map, zobrist_hash_map: &'a ZobristHash) -> Self {// zobrist_hashを初期化するlet mut zobrist_hash = 0;// 各オブジェクトの位置を表すbitsetを初期化し,位置を記録していくlet mut jewelry_map = BitSet::new(N * N);let mut gunpowder_map = BitSet::new(N * N);let mut block_map = BitSet::new(N * N);let mut probe_map = BitSet::new(N * N);// mapからプレイヤーの初期位置を探すlet mut pos = (!0, !0);for y in 0..N {for x in 0..N {if map.S[y][x] == 'S' {pos = (y, x);zobrist_hash ^= zobrist_hash_map.player_hash[y][x];} else if map.S[y][x] == 'K' {zobrist_hash ^= zobrist_hash_map.key_hash[y][x];} else if map.S[y][x] == 'J' {jewelry_map.set(y * N + x, true);} else if map.S[y][x] == 'F' {gunpowder_map.set(y * N + x, true);} else if map.S[y][x] == 'E' {probe_map.set(y * N + x, true);}}}Self {turn: 0,is_done: false,evaluated_score: 0,jewelry_map,gunpowder_map,block_map,probe_map,jewelry: 0,gunpowder: 0,has_key: false,pos,hp: H,output: vec![],zobrist_hash,zobrist_hash_map,}}// 評価関数pub fn evaluate_score(&mut self, map: &Map) {self.evaluated_score = 0;// これまでの獲得宝石数self.evaluated_score += self.jewelry;// 残りの体力self.evaluated_score += self.hp;// ターンを無駄にかけることに対してペナルティself.evaluated_score -= self.turn;// 鍵の有無やゲームクリアしているかどうかについての評価if self.has_key && self.is_done {// 鍵を持っているかつゴールしたself.evaluated_score += 10000;} else if self.has_key && !self.is_done{// 鍵を持っているかつゴールしていないself.evaluated_score += 1500;// ゴールへの距離が近いほどよいとしたい// self.evaluated_score -= self.get_distance_to_destination('G');// self.evaluated_score += (500 / self.get_distance_to_destination( 'G'));self.evaluated_score -= (self.pos.0.abs_diff(map.goal.0) + self.pos.1.abs_diff(map.goal.1)) as i64;} else {// それ以外は鍵を持っていないしゴールもしていない// 鍵への距離が近いほどよいとしたい// self.evaluated_score -= self.get_distance_to_destination('K');// self.evaluated_score += (500 / self.get_distance_to_destination('K'));self.evaluated_score -= (self.pos.0.abs_diff(map.key.0) + self.pos.1.abs_diff(map.key.1)) as i64;}// ゴールしてないかつ体力が切れたなら大幅減点if !self.is_done && self.hp <= 0 {self.evaluated_score -= 10000;}}// 現在地から目的地へのパスを返すpub fn get_path_to_destination(&self, destination: (usize, usize), map: &Map) -> Vec<usize> {let mut dist = INF;let mut prev = vec![!0; N*N]; // 経路復元// 各マップについて,幅優先探索で最も近いコインを探すlet mut deque = VecDeque::new();let mut visited = vec![vec![false; N]; N];deque.push_back((self.pos.0, self.pos.1, 0));visited[self.pos.0][self.pos.1] = true;while let Some((frm_y, frm_x, dist_frm)) = deque.pop_front() {// 目的地なら位置を返すif destination.0 ==frm_y && destination.1 == frm_x {dist = dist_frm;break;}for d in 0..4 {let next_y = frm_y.wrapping_add(DIJ[d].0);let next_x = frm_x.wrapping_add(DIJ[d].1);// 移動: 範囲内で,訪問済みでも壁でもブロックても探知機でもないなら移動可能if next_x < N && next_y < N && !visited[next_y][next_x] && !map.wall[next_y * N + next_x] && !self.block_map[next_y * N + next_x] &&!self.probe_map[next_y * N + next_x] {deque.push_back((next_y, next_x, dist_frm + 1));visited[next_y][next_x] = true;prev[next_y * N + next_x] = frm_y * N + frm_x;}}}// 経路復元let mut path = vec![];let mut t = destination.0 * N + destination.1;let mut last = (!0, !0);// while t != self.pos.0 * N + self.pos.1 {while t != !0 {if last.0 != !0 && last.1 != !0 {// 現在地からlastへ進む方向を取るlet d = if last.0 > t / N {1} else if last.0 < t / N {0} else if last.1 > t % N {3} else if last.1 < t % N {2} else {unreachable!()};path.push(d);}last = (t / N, t % N);t = prev[t];}path.reverse();path}// マンハッタン距離の近い宝石の場所上位5個をとってくる// ただし,鍵が近ければ強制的に鍵の場所だけを返すpub fn search_target(&self, map: &Map) -> Vec<(usize, usize)> {let mut targets = vec![];// 鍵が近ければ鍵を返すif self.pos.0.abs_diff(map.key.0) + self.pos.1.abs_diff(map.key.1) <= 20 && !self.has_key {targets.push((map.key.0, map.key.1));return targets;}// 宝石or火薬let mut jewelry_fire = vec![];for &(j_y, j_x) in &map.jewelry {// 既に取ってるなら飛ばすif !self.jewelry_map[j_y * N + j_x] {continue;}let d = self.pos.0.abs_diff(j_y) + self.pos.1.abs_diff(j_x);jewelry_fire.push((d, (j_y, j_x)));}for &(g_y, g_x) in &map.gunpowder {if !self.gunpowder_map[g_y * N + g_x] {continue;}let d = self.pos.0.abs_diff(g_y) + self.pos.1.abs_diff(g_x);jewelry_fire.push((d, (g_y, g_x)));}jewelry_fire.sort();for i in 0..5 {targets.push((jewelry_fire[i].1));}targets}// 1マス進むのをビームサーチの1stepとみなすときの全ての合法手を返すpub fn get_legal_actions_of_single_cell(&self, map: &Map) -> Vec<Action> {let mut legal_actions = vec![];// 上下左右の4方向を調べるfor d in 0..4 {let next_y = self.pos.0.wrapping_add(DIJ[d].0);let next_x = self.pos.1.wrapping_add(DIJ[d].1);// 移動: 範囲内で,壁でもブロックでも探知機でもないなら移動可能if next_x < N && next_y < N && !map.wall[next_y * N + next_x] && !self.block_map[next_y * N + next_x] && !self.probe_map[next_y * N +next_x] {// 前回の行動を見て,戻るに相当することをしようとしているなら枝刈りする(LRと動くなど.これはSで代替可能)// if self.prev_action.0 == 'M' && (self.prev_action.1 + d) % 4 == 1 {continue;}legal_actions.push(('M', d));}// ブロック生成: 範囲内で,空なら設置可能 (スタート地点も含む)if next_x < N && next_y < N && !map.wall[next_y * N + next_x] && !self.block_map[next_y * N + next_x] && !self.probe_map[next_y * N +next_x]&& !self.jewelry_map[next_y * N + next_x] && !self.gunpowder_map[next_y * N + next_x] && !(next_y == map.goal.0 && next_x == map.goal.1)&& !(!self.has_key && next_y == map.key.0 && next_x == map.key.1) {legal_actions.push(('B', d));}// ブロック破壊: 範囲内で,ブロックなら破壊可能if next_x < N && next_y < N && self.block_map[next_y * N + next_x] {legal_actions.push(('B', d));}// [todo] 火炎放射(=探知機破壊): 範囲内で,火薬があり,上下左右の延長方向に探知機があれば破壊可能}// 何もしないのは常に合法手legal_actions.push(('S', !0));legal_actions}// 宝石or鍵or扉から宝石or鍵or扉へ進むのをビームサーチの1stepとみなすときの全ての合法手を返すpub fn get_legal_actions(&self, map: &Map) -> Vec<Vec<Action>> {let mut legal_action_list = vec![];// let mut legal_actions = vec![];// // 上下左右の4方向を調べる// for d in 0..4 {// let next_y = self.pos.0.wrapping_add(DIJ[d].0);// let next_x = self.pos.1.wrapping_add(DIJ[d].1);// // 移動: 範囲内で,壁でもブロックでも探知機でもないなら移動可能// if next_x < N && next_y < N && !map.wall[next_y * N + next_x] && !self.block_map[next_y * N + next_x] && !self.probe_map[next_y * N +next_x] {// // 前回の行動を見て,戻るに相当することをしようとしているなら枝刈りする(LRと動くなど.これはSで代替可能)// // if self.prev_action.0 == 'M' && (self.prev_action.1 + d) % 4 == 1 {continue;}// legal_actions.push(('M', d));// }// // ブロック生成: 範囲内で,空なら設置可能 (スタート地点も含む)// if next_x < N && next_y < N && !map.wall[next_y * N + next_x] && !self.block_map[next_y * N + next_x] && !self.probe_map[next_y * N +next_x]// && !self.jewelry_map[next_y * N + next_x] && !self.gunpowder_map[next_y * N + next_x] && !(next_y == map.goal.0 && next_x == map.goal.1)// && !(!self.has_key && next_y == map.key.0 && next_x == map.key.1) {// legal_actions.push(('B', d));// }// // ブロック破壊: 範囲内で,ブロックなら破壊可能// if next_x < N && next_y < N && self.block_map[next_y * N + next_x] {// legal_actions.push(('B', d));// }// // [todo] 火炎放射(=探知機破壊): 範囲内で,火薬があり,上下左右の延長方向に探知機があれば破壊可能// }// // 何もしないのは常に合法手// legal_actions.push(('S', !0));// legal_actionsif self.hp > 200 {let targets = self.search_target(map);for &(t_y, t_x) in &targets {let mut legal_actions = vec![];let path = self.get_path_to_destination((t_y, t_x), map);for &d in &path {// let next_y = self.pos.0.wrapping_add(DIJ[d].0);// let next_x = self.pos.1.wrapping_add(DIJ[d].1);legal_actions.push(('M', d));}legal_action_list.push(legal_actions);}} else if !self.has_key {let mut legal_actions = vec![];let path = self.get_path_to_destination((map.key.0, map.key.1), map);for &d in &path {// let next_y = self.pos.0.wrapping_add(DIJ[d].0);// let next_x = self.pos.1.wrapping_add(DIJ[d].1);legal_actions.push(('M', d));}legal_action_list.push(legal_actions);} else {let mut legal_actions = vec![];let path = self.get_path_to_destination((map.goal.0, map.goal.1), map);for &d in &path {// let next_y = self.pos.0.wrapping_add(DIJ[d].0);// let next_x = self.pos.1.wrapping_add(DIJ[d].1);legal_actions.push(('M', d));}legal_action_list.push(legal_actions);}legal_action_list}// このターンにプレイヤーに当たる探知機の数を見つける// [todo] 高速化したいfn search_danger_probe(&self, map: &Map) -> i64 {let mut num_probe = 0;for p in (0..self.pos.0).rev() {// 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全if map.wall[p * N + self.pos.1] || self.block_map[p * N + self.pos.1] || (self.probe_map[p * N + self.pos.1] && self.turn % map.interval_of_probe[p * N + self.pos.1] != 0) {break;}if self.probe_map[p * N + self.pos.1] && self.turn % map.interval_of_probe[p * N + self.pos.1] == 0 {num_probe += 1;break;}}for p in self.pos.0+1..N {// 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全if map.wall[p * N + self.pos.1] || self.block_map[p * N + self.pos.1] || (self.probe_map[p * N + self.pos.1] && self.turn % map.interval_of_probe[p * N + self.pos.1] != 0) {break;}if self.probe_map[p * N + self.pos.1] && self.turn % map.interval_of_probe[p * N + self.pos.1] == 0 {num_probe += 1;break;}}for p in (0..self.pos.1).rev() {// 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全if map.wall[self.pos.0 * N + p] || self.block_map[self.pos.0 * N + p] || (self.probe_map[self.pos.0 * N + p] && self.turn % map.interval_of_probe[self.pos.0 * N + p] != 0) {break;}if self.probe_map[self.pos.0 * N + p] && self.turn % map.interval_of_probe[self.pos.0 * N + p] == 0 {num_probe += 1;break;}}for p in self.pos.1+1..N {// 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全if map.wall[self.pos.0 * N + p] || self.block_map[self.pos.0 * N + p] || (self.probe_map[self.pos.0 * N + p] && self.turn % map.interval_of_probe[self.pos.0 * N + p] != 0) {break;}if self.probe_map[self.pos.0 * N + p] && self.turn % map.interval_of_probe[self.pos.0 * N + p] == 0 {num_probe += 1;break;}}num_probe}// 指定したactionを各マップに施すpub fn advance(&mut self, map: &Map, action: Action) {// ターン加算self.turn += 1;// 1ターンで必ず体力を1消耗するself.hp -= 1;// 行動の種類によって分岐するmatch action.0 {'S' => {// outputへ入れるself.output.push((action.0, 'x'));},'M' => {let d = action.1;let next_y = self.pos.0.wrapping_add(DIJ[d].0);let next_x = self.pos.1.wrapping_add(DIJ[d].1);// 移動前のプレイヤー位置に関して,zobrist hashのxorして消すself.zobrist_hash ^= self.zobrist_hash_map.player_hash[self.pos.0][self.pos.1];// 移動し,zobrist hashも更新self.pos = (next_y, next_x);self.zobrist_hash ^= self.zobrist_hash_map.player_hash[next_y][next_x];if next_y == map.key.0 && next_x == map.key.1 {// 鍵の取得self.has_key = true;self.zobrist_hash ^= self.zobrist_hash_map.key_hash[next_y][next_x];} else if next_y == map.goal.0 && next_x == map.goal.1 && self.has_key {// ゲームクリアself.is_done = true;} else if self.jewelry_map[next_y * N + next_x] {// 宝石の取得self.jewelry += 10;self.jewelry_map.set(next_y * N + next_x, false);self.zobrist_hash ^= self.zobrist_hash_map.jewelry_hash[next_y][next_x];} else if self.gunpowder_map[next_y * N + next_x] {// 火薬の取得self.gunpowder += 1;self.gunpowder_map.set(next_y * N + next_x, false);self.zobrist_hash ^= self.zobrist_hash_map.gunpowder_hash[next_y][next_x];}// outputへ入れるself.output.push((action.0, DIR[action.1]));},'B' => {let d = action.1;let next_y = self.pos.0.wrapping_add(DIJ[d].0);let next_x = self.pos.1.wrapping_add(DIJ[d].1);// 生成・破壊は隣にあるかないかで分岐if self.block_map[next_y * N + next_x] {self.block_map.set(next_y * N + next_x, false);self.zobrist_hash ^= self.zobrist_hash_map.block_hash[next_y][next_x];} else {self.block_map.set(next_y * N + next_x, true);self.zobrist_hash ^= self.zobrist_hash_map.block_hash[next_y][next_x];}// outputへ入れるself.output.push((action.0, DIR[action.1]));},'F' => (),_ => unreachable!(),}// 今いる場所の上下左右の延長線上で,このターンに作動する探知機が存在するかどうか調べるif !self.is_done {let num_probes = self.search_danger_probe(map);self.hp -= num_probes * map.D;}}// 指定したactionが施された盤面を元の状態に戻すpub fn roll_back(&mut self, map: &Map, action: Action) {// ターン減算self.turn -= 1;// 体力をとりあえず1戻すself.hp += 1;// 行動の種類によって分岐するmatch action.0 {'S' => {// 行動を除外self.output.pop();},'M' => {let d = action.1;// 現在地→前いたところへ戻るための逆操作のインデックスをもらうlet oposite_d = if d % 2 == 0 {d + 1} else {d - 1};// 前にいた座標を取得let prev_y = self.pos.0.wrapping_add(DIJ[oposite_d].0);let prev_x = self.pos.1.wrapping_add(DIJ[oposite_d].1);// 現在地のzobrist hashのxorself.zobrist_hash ^= self.zobrist_hash_map.player_hash[self.pos.0][self.pos.1];// 前いた座標のzobrist hashのxorself.zobrist_hash ^= self.zobrist_hash_map.player_hash[prev_y][prev_x];// 現在地のマス目がどんなものだったかif self.pos.0 == map.key.0 && self.pos.1 == map.key.1 {// 鍵を返すself.has_key = false;self.zobrist_hash ^= self.zobrist_hash_map.key_hash[self.pos.0][self.pos.1];} else if self.pos.0 == map.goal.0 && self.pos.1 == map.goal.1 && self.has_key {// ゲームクリアself.is_done = false;} else if self.jewelry_map[self.pos.0 * N + self.pos.1] {// 宝石を返すself.jewelry -= 10;self.jewelry_map.set(self.pos.0 * N + self.pos.1, true);self.zobrist_hash ^= self.zobrist_hash_map.jewelry_hash[self.pos.0][self.pos.1];} else if self.gunpowder_map[self.pos.0 * N + self.pos.1] {// 火薬を返すself.gunpowder -= 1;self.gunpowder_map.set(self.pos.0 * N + self.pos.1, true);self.zobrist_hash ^= self.zobrist_hash_map.gunpowder_hash[self.pos.0][self.pos.1];}// 行動を削除self.output.pop();// 現在地を前いたところに戻すself.pos = (prev_y, prev_x);},'B' => {// ブロックの場合は同じ行動をするが,outputからは消すlet d = action.1;let next_y = self.pos.0.wrapping_add(DIJ[d].0);let next_x = self.pos.1.wrapping_add(DIJ[d].1);// 生成・破壊は隣にあるかないかで分岐if self.block_map[next_y * N + next_x] {self.block_map.set(next_y * N + next_x, false);self.zobrist_hash ^= self.zobrist_hash_map.block_hash[next_y][next_x];} else {self.block_map.set(next_y * N + next_x, true);self.zobrist_hash ^= self.zobrist_hash_map.block_hash[next_y][next_x];}// 行動を削除self.output.pop();},'F' => (),_ => unreachable!(),}// 今いる場所の上下左右の延長線上で,このターンに作動する探知機が存在するかどうか調べるif !self.is_done {let num_probes = self.search_danger_probe(map);self.hp -= num_probes * map.D;}}// 回答を出力するpub fn print(&self) {for &(action, dir) in &self.output {if action == 'S' {println!("{}", action);} else {println!("{} {}", action, dir);}}}}// Stateをbinaryheapに入れるとき,評価値の大きい順に取り出すため,partialordを実装する// impl Ord for State {impl<'a> Ord for State<'a> {fn cmp(&self, other: &Self) -> std::cmp::Ordering {self.evaluated_score.cmp(&other.evaluated_score)}}// impl PartialEq for State {impl<'a> PartialEq for State<'a> {fn eq(&self, other: &Self) -> bool {self.evaluated_score == other.evaluated_score}}// impl Eq for State {} // ここは空でOKimpl<'a> Eq for State<'a> {} // ここは空でOK// impl PartialOrd for State {impl<'a> PartialOrd for State<'a> {fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {self.evaluated_score.partial_cmp(&other.evaluated_score)}}// ある座標にプレイヤー,ブロック,探知機,宝石,火薬,鍵が存在することをハッシュに変換する#[derive(Clone)]struct ZobristHash {player_hash: Vec<Vec<u128>>, // 座標pにプレイヤーが存在することに対応するハッシュ値block_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値probe_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値jewelry_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値gunpowder_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値key_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値}impl ZobristHash {fn new() -> Self {let mut rng = Xoshiro256::new(8192);let mut player_hash = vec![vec![0; N]; N];let mut block_hash = vec![vec![0; N]; N];let mut probe_hash = vec![vec![0; N]; N];let mut jewelry_hash = vec![vec![0; N]; N];let mut gunpowder_hash = vec![vec![0; N]; N];let mut key_hash = vec![vec![0; N]; N];for y in 0..N {for x in 0..N {player_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);block_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);probe_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);jewelry_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);gunpowder_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);key_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);}}Self { player_hash, block_hash, probe_hash, jewelry_hash, gunpowder_hash, key_hash }}}// ビームサーチfn beam_search<'a>(state: &'a State<'a>, map: &Map, beam_width: usize, beam_depth: usize) -> Option<State<'a>> {let mut best_state = state.clone();let mut now_beam = BinaryHeap::new();now_beam.push(state.clone());let mut zobrist_hash_set = HashSet::new();for _ in 0..beam_depth {let mut next_beam = BinaryHeap::new();for _ in 0..beam_width {if now_beam.is_empty() {break;}let now_state = now_beam.pop().unwrap();if now_state.is_done {continue;}let legal_action_list = now_state.get_legal_actions(map);// eprintln!("legal_actions: {:?}", legal_actions);for i in 0..legal_action_list.len() {let mut next_state = now_state.clone();for &action in &legal_action_list[i] {next_state.advance(map, action);// eprintln!("action: {:?}", action);// eprintln!("pos: {:?}", next_state.pos);// eprintln!("jewelry: {}", next_state.jewelry);}// 同一盤面が評価済みかどうかで評価値を変えるif zobrist_hash_set.contains(&next_state.zobrist_hash) {continue;} else {next_state.evaluate_score(map);zobrist_hash_set.insert(next_state.zobrist_hash);}next_beam.push(next_state);}}if next_beam.is_empty() {eprintln!("empty");break;}if best_state.evaluated_score <= next_beam.peek().unwrap().evaluated_score && next_beam.peek().unwrap().is_done {best_state = next_beam.peek().unwrap().clone();}now_beam.clear();while now_beam.len() < beam_width {if let Some(state) = next_beam.pop() {now_beam.push(state);} else {break;}}}Some(best_state)}fn main() {get_time();let map = Map::new();let zobrist_hash_map = ZobristHash::new();let mut state = State::new(&map, &zobrist_hash_map);// ビームサーチを回すif let Some(bs_state) = beam_search(&state, &map, 30, H as usize) {bs_state.print();eprintln!("evaluated score: {}", bs_state.evaluated_score);eprintln!("game score: {}", bs_state.jewelry);eprintln!("turn: {}", bs_state.turn);eprintln!("time: {}", get_time());} else {eprintln!("error");eprintln!("time: {}", get_time());}}