結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 r3yohei
|
| 提出日時 | 2023-05-10 20:04:57 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 2,992 ms / 3,000 ms |
| コード長 | 41,496 bytes |
| コンパイル時間 | 4,341 ms |
| コンパイル使用メモリ | 186,256 KB |
| 実行使用メモリ | 19,568 KB |
| スコア | 101,330 |
| 最終ジャッジ日時 | 2023-05-10 20:08:02 |
| 合計ジャッジ時間 | 178,487 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,401 ms
19,024 KB |
| testcase_01 | AC | 1,608 ms
16,012 KB |
| testcase_02 | AC | 1,266 ms
12,156 KB |
| testcase_03 | AC | 1,486 ms
10,668 KB |
| testcase_04 | AC | 856 ms
11,424 KB |
| testcase_05 | AC | 2,698 ms
17,752 KB |
| testcase_06 | AC | 2,343 ms
16,376 KB |
| testcase_07 | AC | 1,242 ms
11,116 KB |
| testcase_08 | AC | 1,609 ms
14,192 KB |
| testcase_09 | AC | 1,147 ms
10,808 KB |
| testcase_10 | AC | 2,992 ms
19,084 KB |
| testcase_11 | AC | 2,658 ms
16,480 KB |
| testcase_12 | AC | 1,978 ms
16,220 KB |
| testcase_13 | AC | 1,272 ms
12,172 KB |
| testcase_14 | AC | 1,554 ms
10,804 KB |
| testcase_15 | AC | 1,988 ms
17,860 KB |
| testcase_16 | AC | 1,465 ms
15,928 KB |
| testcase_17 | AC | 1,980 ms
15,132 KB |
| testcase_18 | AC | 1,407 ms
10,932 KB |
| testcase_19 | AC | 1,092 ms
11,224 KB |
| testcase_20 | AC | 2,958 ms
19,568 KB |
| testcase_21 | AC | 2,002 ms
14,592 KB |
| testcase_22 | AC | 1,231 ms
10,712 KB |
| testcase_23 | AC | 1,220 ms
12,792 KB |
| testcase_24 | AC | 976 ms
11,776 KB |
| testcase_25 | AC | 2,432 ms
19,496 KB |
| testcase_26 | AC | 1,663 ms
16,556 KB |
| testcase_27 | AC | 1,958 ms
16,268 KB |
| testcase_28 | AC | 1,065 ms
10,460 KB |
| testcase_29 | AC | 1,167 ms
10,748 KB |
| testcase_30 | AC | 2,188 ms
16,492 KB |
| testcase_31 | AC | 1,740 ms
16,584 KB |
| testcase_32 | AC | 1,462 ms
15,220 KB |
| testcase_33 | AC | 1,034 ms
11,972 KB |
| testcase_34 | AC | 1,235 ms
10,516 KB |
| testcase_35 | AC | 2,139 ms
18,224 KB |
| testcase_36 | AC | 1,507 ms
14,288 KB |
| testcase_37 | AC | 1,856 ms
15,060 KB |
| testcase_38 | AC | 1,408 ms
12,268 KB |
| testcase_39 | AC | 1,040 ms
10,992 KB |
| testcase_40 | AC | 2,530 ms
17,488 KB |
| testcase_41 | AC | 1,917 ms
15,652 KB |
| testcase_42 | AC | 1,172 ms
12,680 KB |
| testcase_43 | AC | 1,280 ms
12,148 KB |
| testcase_44 | AC | 964 ms
11,388 KB |
| testcase_45 | AC | 2,641 ms
18,564 KB |
| testcase_46 | AC | 1,812 ms
16,368 KB |
| testcase_47 | AC | 1,755 ms
15,332 KB |
| testcase_48 | AC | 1,017 ms
11,920 KB |
| testcase_49 | AC | 945 ms
11,232 KB |
| testcase_50 | AC | 2,153 ms
17,800 KB |
| testcase_51 | AC | 2,008 ms
14,764 KB |
| testcase_52 | AC | 1,252 ms
11,828 KB |
| testcase_53 | AC | 1,533 ms
11,288 KB |
| testcase_54 | AC | 1,044 ms
11,720 KB |
| testcase_55 | AC | 2,653 ms
19,028 KB |
| testcase_56 | AC | 1,525 ms
11,944 KB |
| testcase_57 | AC | 1,474 ms
14,764 KB |
| testcase_58 | AC | 899 ms
10,960 KB |
| testcase_59 | AC | 1,420 ms
10,732 KB |
| testcase_60 | AC | 2,358 ms
17,048 KB |
| testcase_61 | AC | 2,081 ms
17,888 KB |
| testcase_62 | AC | 1,642 ms
13,936 KB |
| testcase_63 | AC | 1,207 ms
10,324 KB |
| testcase_64 | AC | 1,001 ms
10,684 KB |
| testcase_65 | AC | 2,369 ms
17,544 KB |
| testcase_66 | AC | 1,609 ms
17,388 KB |
| testcase_67 | AC | 1,481 ms
13,444 KB |
| testcase_68 | AC | 1,212 ms
10,952 KB |
| testcase_69 | AC | 913 ms
11,320 KB |
| testcase_70 | AC | 2,341 ms
18,448 KB |
| testcase_71 | AC | 1,872 ms
16,640 KB |
| testcase_72 | AC | 1,244 ms
13,184 KB |
| testcase_73 | AC | 1,216 ms
10,360 KB |
| testcase_74 | AC | 1,325 ms
11,480 KB |
| testcase_75 | AC | 2,197 ms
16,976 KB |
| testcase_76 | AC | 1,647 ms
15,760 KB |
| testcase_77 | AC | 1,452 ms
16,460 KB |
| testcase_78 | AC | 1,209 ms
12,160 KB |
| testcase_79 | AC | 1,001 ms
10,392 KB |
| testcase_80 | AC | 2,155 ms
16,416 KB |
| testcase_81 | AC | 1,764 ms
14,456 KB |
| testcase_82 | AC | 2,228 ms
15,480 KB |
| testcase_83 | AC | 1,528 ms
14,572 KB |
| testcase_84 | AC | 1,815 ms
10,612 KB |
| testcase_85 | AC | 2,599 ms
17,936 KB |
| testcase_86 | AC | 2,199 ms
14,908 KB |
| testcase_87 | AC | 1,650 ms
14,620 KB |
| testcase_88 | AC | 1,331 ms
11,928 KB |
| testcase_89 | AC | 1,457 ms
12,036 KB |
| testcase_90 | AC | 1,992 ms
17,620 KB |
| testcase_91 | AC | 1,629 ms
15,544 KB |
| testcase_92 | AC | 1,500 ms
12,684 KB |
| testcase_93 | AC | 1,455 ms
12,088 KB |
| testcase_94 | AC | 1,067 ms
10,700 KB |
| testcase_95 | AC | 2,394 ms
19,408 KB |
| testcase_96 | AC | 1,937 ms
15,856 KB |
| testcase_97 | AC | 1,672 ms
14,088 KB |
| testcase_98 | AC | 1,381 ms
14,512 KB |
| testcase_99 | AC | 917 ms
9,988 KB |
ソースコード
#![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/b00be62bf68c9fb6055d22eb77c17e14
pub 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 collection
pub 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, // 宝石位置を表すbitset
gunpowder_map: BitSet, // 火薬位置を表すbitset
block_map: BitSet, // ブロック位置を表すbitset
probe_map: BitSet, // 探知機位置を表すbitset
pos: (usize, usize), // プレイヤーの現在地の(y, x)
hp: i64, // プレイヤーの体力
jewelry: i64, // 宝石の数 (これx10が実際のゲームスコア)
gunpowder: i64, // 火薬の数
has_key: bool, // 鍵を持っているかどうか
search_range: usize, // 次に探しに行く宝石を列挙する数
search_key_threshold: usize, // 自分から見て鍵のマンハッタン距離がこれ以内なら鍵を優先的に取りに行く
emergency_hp_threshold_to_key: i64, // 残り体力がこれ以下かつ鍵を持っていなければ鍵へ向かう
emergency_hp_threshold_to_goal: i64, // 残り体力がこれ以下になったらゴールへ向かう
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);
}
}
}
// 探索を工夫すればここは攻められる
let emergency_hp_threshold_to_key = if map.D == 3 {
100
} else if map.D == 4 {
200
} else if map.D == 5 {
300
} else if map.D == 6 {
400
} else {
500
};
let emergency_hp_threshold_to_goal = emergency_hp_threshold_to_key / 2;
Self {
turn: 0,
is_done: false,
evaluated_score: 0,
jewelry_map,
gunpowder_map,
block_map,
probe_map,
jewelry: 0,
gunpowder: 0,
has_key: false,
search_range: 3, // [ToDo] ハードコーディングを辞める
search_key_threshold: 20, // [ToDo] ハードコーディングを辞める
emergency_hp_threshold_to_key,
emergency_hp_threshold_to_goal,
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.hp >= 0 {
// 鍵を持っているかつゴールした
self.evaluated_score += 1000;
} else if self.has_key && !self.is_done && self.hp >= 0 {
// 鍵を持っているかつゴールしていない
self.evaluated_score += 500;
// ゴールへの距離が近いほどよいとしたい
// 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;
self.is_done = true;
}
}
// 現在地から目的地へのパスをBFSで調べ，経路復元して返す
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 != !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
}
// マンハッタン距離の近い宝石の場所上位いくらかとってくる
// ただし，鍵が近ければ強制的に鍵の場所だけを返す
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) <= self.search_key_threshold && !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..self.search_range {
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 dist_to_key = (self.pos.0.abs_diff(map.key.0) + self.pos.1.abs_diff(map.key.1)) as i64;
let dist_to_goal = (self.pos.0.abs_diff(map.goal.0) + self.pos.1.abs_diff(map.goal.1)) as i64;
if self.hp >= dist_to_key + self.emergency_hp_threshold_to_key || (self.has_key && self.hp >= dist_to_goal + self.emergency_hp_threshold_to_goal) {
// 鍵探索/ゴール到達まで猶予があるなら周囲の宝石を探す
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);
// 取得したパスをストレートに渡るべきかどうかを判断したい
let mut turn = self.turn;
let mut crt_pos = self.pos;
for &d in &path {
// [ToDo] 進んだほうがいいのか，立ち止まったりブロック生成などしたほうがいいのかを都度確認する
let next_y = crt_pos.0.wrapping_add(DIJ[d].0);
let next_x = crt_pos.1.wrapping_add(DIJ[d].1);
let (mut num_probe_stay, _) = self.search_danger_probe(map, turn, crt_pos.0, crt_pos.1);
let (mut num_probe_move, _) = self.search_danger_probe(map, turn + 1, next_y, next_x);
// 止まったほうがダメージが少ないとき
while num_probe_stay < num_probe_move {
// 止まる
legal_actions.push(('S', !0));
turn += 1;
// ターンを更新して探知される数を確認する
let (mut n1, _) = self.search_danger_probe(map, turn, crt_pos.0, crt_pos.1);
let (mut n2, _) = self.search_danger_probe(map, turn + 1, next_y, next_x);
num_probe_stay = n1;
num_probe_move = n2;
}
// 進んだほうが良くなったら，進む
turn += 1;
crt_pos = (next_y, next_x);
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);
// 取得したパスをストレートに渡るべきかどうかを判断したい
let mut turn = self.turn;
let mut crt_pos = self.pos;
for &d in &path {
let next_y = crt_pos.0.wrapping_add(DIJ[d].0);
let next_x = crt_pos.1.wrapping_add(DIJ[d].1);
let (mut num_probe_stay, _) = self.search_danger_probe(map, turn, crt_pos.0, crt_pos.1);
let (mut num_probe_move, _) = self.search_danger_probe(map, turn + 1, next_y, next_x);
// 止まったほうがダメージが少ないとき
while num_probe_stay < num_probe_move {
// 止まる
legal_actions.push(('S', !0));
turn += 1;
// ターンを更新して探知される数を確認する
let (mut n1, _) = self.search_danger_probe(map, turn, crt_pos.0, crt_pos.1);
let (mut n2, _) = self.search_danger_probe(map, turn + 1, next_y, next_x);
num_probe_stay = n1;
num_probe_move = n2;
}
// 進んだほうが良くなったら，進む
turn += 1;
crt_pos = (next_y, next_x);
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);
let mut turn = self.turn;
let mut crt_pos = self.pos;
for &d in &path {
let next_y = crt_pos.0.wrapping_add(DIJ[d].0);
let next_x = crt_pos.1.wrapping_add(DIJ[d].1);
let (mut num_probe_stay, _) = self.search_danger_probe(map, turn, crt_pos.0, crt_pos.1);
let (mut num_probe_move, _) = self.search_danger_probe(map, turn + 1, next_y, next_x);
// 止まったほうがダメージが少ないとき
while num_probe_stay < num_probe_move {
// 止まる
legal_actions.push(('S', !0));
turn += 1;
// ターンを更新して探知される数を確認する
let (mut n1, _) = self.search_danger_probe(map, turn, crt_pos.0, crt_pos.1);
let (mut n2, _) = self.search_danger_probe(map, turn + 1, next_y, next_x);
num_probe_stay = n1;
num_probe_move = n2;
}
// 進んだほうが良くなったら，進む
turn += 1;
crt_pos = (next_y, next_x);
legal_actions.push(('M', d));
}
legal_action_list.push(legal_actions);
}
legal_action_list
}
// このターンに地点(y, x)に当たる探知機の方向を見つける
// [todo] 高速化したい
fn search_danger_probe(&self, map: &Map, turn: i64, y: usize, x: usize) -> (i64, Vec<bool>) {
let mut is_detected = vec![false; 4];
for p in (0..y).rev() {
// 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全
if map.wall[p * N + x] || self.block_map[p * N + x] || (self.probe_map[p * N + x] && turn % map.interval_of_probe[p * N + x] != 0) {
break;
}
if self.probe_map[p * N + x] && turn % map.interval_of_probe[p * N + x] == 0 {
is_detected[0] = true;
break;
}
}
for p in y+1..N {
// 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全
if map.wall[p * N + x] || self.block_map[p * N + x] || (self.probe_map[p * N + x] && turn % map.interval_of_probe[p * N + x] != 0) {
break;
}
if self.probe_map[p * N + x] && turn % map.interval_of_probe[p * N + x] == 0 {
is_detected[1] = true;
break;
}
}
for p in (0..x).rev() {
// 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全
if map.wall[y * N + p] || self.block_map[y * N + p] || (self.probe_map[y * N + p] && turn % map.interval_of_probe[y * N + p] != 0) {
break;
}
if self.probe_map[y * N + p] && turn % map.interval_of_probe[y * N + p] == 0 {
is_detected[2] = true;
break;
}
}
for p in x+1..N {
// 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全
if map.wall[y * N + p] || self.block_map[y * N + p] || (self.probe_map[y * N + p] && turn % map.interval_of_probe[y * N + p] != 0) {
break;
}
if self.probe_map[y * N + p] && turn % map.interval_of_probe[y * N + p] == 0 {
is_detected[3] = true;
break;
}
}
let mut num_probes = 0;
for &e in &is_detected {
if e {num_probes += 1;}
}
(num_probes, is_detected)
}
// 指定した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.turn, self.pos.0, self.pos.1);
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<'a> Ord for State<'a> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.evaluated_score.cmp(&other.evaluated_score)
}
}
impl<'a> PartialEq for State<'a> {
fn eq(&self, other: &Self) -> bool {
self.evaluated_score == other.evaluated_score
}
}
impl<'a> Eq for State<'a> {} // ここは空でOK
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);
next_state.evaluate_score(map);
// 宝石から宝石への移動にしたことで，ゲーム上では複数のアクションを一気にやるようになってる
// 途中でも終了判定を入れる必要がある
if next_state.is_done {break;}
// eprintln!("action: {:?}", action);
// eprintln!("pos: {:?}", next_state.pos);
// eprintln!("jewelry: {}", next_state.jewelry);
}
// 同一盤面が評価済みかどうかで評価値を変える
if zobrist_hash_set.contains(&next_state.zobrist_hash) {
continue;
} else {
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, 400, H as usize) {
bs_state.print();
eprintln!("turn: {}", bs_state.turn);
eprintln!("evaluated score: {}", bs_state.evaluated_score);
eprintln!("D: {}", map.D);
eprintln!("remained HP: {}", bs_state.hp);
eprintln!("time: {}", get_time());
eprintln!("game score: {}", bs_state.jewelry);
} else {
eprintln!("error");
eprintln!("time: {}", get_time());
}
}