結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 rhoo
|
| 提出日時 | 2023-04-16 10:09:21 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 15,885 bytes |
| コンパイル時間 | 5,700 ms |
| コンパイル使用メモリ | 189,092 KB |
| 実行使用メモリ | 229,352 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-04-16 10:09:36 |
| 合計ジャッジ時間 | 14,573 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
コンパイルメッセージ
warning: variable `HP` is assigned to, but never used
--> Main.rs:290:13
|
290 | let mut HP=H+2;
| ^^
|
= note: consider using `_HP` instead
= note: `#[warn(unused_variables)]` on by default
warning: variable `juwels` is assigned to, but never used
--> Main.rs:291:13
|
291 | let mut juwels=0;
| ^^^^^^
|
= note: consider using `_juwels` instead
warning: field `goal` is never read
--> Main.rs:451:5
|
445 | struct In{
| -- field in this struct
...
451 | goal:usize,
| ^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: function `get_time` is never used
--> Main.rs:636:4
|
636 | fn get_time()->f64{
| ^^^^^^^^
warning: 4 warnings emitted
ソースコード
#![allow(non_snake_case)]
#[cfg(not(local))]macro_rules! eprintln{($($_:tt)*)=>{}}
const MAX_TURN:usize=40;
struct BUF{
base:i64,
dist:Vec<i64>,
prev:Vec<Vec<usize>>,
que:Vec<VecDeque<(i64,usize,usize)>>,
// heap:BinaryHeap<Reverse<S<i64,(usize,usize,usize)>>>
}
impl BUF{
fn new()->BUF{
BUF{
base:i64::MAX,
dist:vec![i64::MAX;N2],
prev:vec![vec![!0;MAX_TURN];N2],
que:vec![VecDeque::new();16],
// heap:BinaryHeap::new()
}
}
fn reset(&mut self){
self.base-=100000;
for i in 0..16{
self.que[i].clear();
}
// self.heap.clear();
}
}
// todo
fn score(juwels:usize,key:bool)->f64{
const KEY_BONUS:f64=2.5;
juwels as f64
+if key{
KEY_BONUS
} else {
0.
}
}
#[derive(Clone)]
struct Node{
hist:List<usize>,
seen:Vec<u8>,
pos:usize,
turn:usize,
HP:i64,
juwels:usize,
}
impl Node{
fn new(input:&In)->Node{
Node{
hist:Cons(input.start,Rc::new(Nil)),
seen:vec![0;(input.I>>3)+1],
pos:input.start,
turn:0,
HP:H,
juwels:0,
}
}
fn get(&self,id:usize)->bool{
let (a,b)=(id>>3,id&7);
self.seen[a]>>b&1==1
}
fn get_routes(&self,input:&In,BF:&mut BUF)->Vec<(Vec<usize>,i64,Cell)>{
// todo
const C:usize=3;
let R:i64=50.min(self.HP);
let old=BF.base;
BF.reset();
let mut ret=vec![];
BF.que[0].push_back((BF.base,self.pos,0));
// BF.heap.push(Reverse(S(BF.base,(self.pos,0,0))));
BF.dist[self.pos]=BF.base;
BF.prev[self.pos][0]=!0;
let th=BF.base+R;
while let Some((cost,pos,t))={
if let Some(ty)=(0..16).filter(|&i|!BF.que[i].is_empty()).min_by_key(|&i|BF.que[i].front().unwrap().0){
let (cost,pos,t)=BF.que[ty].pop_front().unwrap();
Some((cost,pos,t))
}
else{
None
}
}{
// while let Some(Reverse(S(cost,(pos,t,ty))))=BF.heap.pop(){
// if let Some((cost,pos,t))=BF.que[ty].pop_front(){
// BF.heap.push(Reverse(S(cost,(pos,t,ty))));
// }
let turn=(self.turn+t)%60;
let nturn=(turn+1)%60;
let nt=t+1;
for dd in DX{
let np=pos+dd;
let cell=input.grid[np];
let nc=input.damage[np][nturn].0+cost;
let ty=input.damage[np][nturn].1;
if cell==Goal && self.get(0) || matches!(cell,Juwel(id) if !self.get(id)){
if dd==0{
continue;
}
let mut route=vec![np];
let mut pos=(pos,t);
loop{
route.push(pos.0);
pos=(BF.prev[pos.0][pos.1],pos.1-1);
if pos.0==!0{
break;
}
}
route.pop();
route.reverse();
ret.push((route,nc-BF.base,cell));
if ret.len()>=C{
return ret;
}
}
else if cell.is_through() && MAX_TURN>nt{
if old>BF.dist[np] && dd!=0{
continue;
}
BF.dist[np]=old-1;
if (BF.dist[np]>nc || dd==0) && th>=nc{
BF.dist[np]=BF.dist[np].min(nc);
// if BF.que[ty].is_empty(){
// BF.heap.push(Reverse(S(nc,(np,nt,ty))));
// }
// else{
BF.que[ty].push_back((nc,np,nt));
// }
BF.prev[np][nt]=pos;
}
}
}
}
ret
}
fn to_cand(&self,input:&In,id:(usize,usize),route:Vec<usize>,diff:i64)->Option<Cand>{
let HP=self.HP-diff;
let pos=*route.last().unwrap();
let key=(self.seen[0]&1==1)|(input.id[pos]==0);
let cost=input.cost(pos,key);
if cost>=HP as f64{
return None;
}
let juwels=self.juwels+1;
Some(
Cand{
parent:id,
HP,
juwels,pos,
turn:self.turn+route.len(),
score:score(juwels,key),
op:route
}
)
}
fn append_cands(&self,input:&In,id:(usize,usize),cands:&mut Vec<Vec<Cand>>,best_score:&mut usize,best:&mut List<usize>,BF:&mut BUF){
let routes=self.get_routes(input,BF);
for (route,diff,cell) in routes{
if let Some(cand)=self.to_cand(input,id,route,diff){
if cell==Goal{
if *best_score<cand.juwels{
*best_score=cand.juwels;
*best=self.hist.append(&cand.op);
}
}
else{
cands[cand.HP as usize].push(cand);
}
}
}
}
}
#[derive(Clone)]
struct Cand{
parent:(usize,usize),
op:Vec<usize>,
pos:usize,
turn:usize,
HP:i64,
juwels:usize,
score:f64,
}
impl Cand{
fn to_node(&self,input:&In,parent:&Node)->Node{
let mut seen=parent.seen.clone();
if let Juwel(id)=input.grid[self.pos]{
seen[id>>3]|=1<<(id&7);
}
Node{
seen,
hist:parent.hist.append(&self.op),
pos:self.pos,
turn:self.turn,
HP:self.HP,
juwels:self.juwels,
}
}
}
struct Beam{
nodes:Vec<Vec<Node>>,
best_score:usize,
best:List<usize>
}
impl Beam{
fn new(node:Node)->Beam{
let mut nodes=vec![vec![];H as usize+1];
nodes[H as usize].push(node);
Beam{
nodes,
best_score:0,
best:Nil
}
}
fn enum_cands(&mut self,input:&In,HP:usize,cands:&mut Vec<Vec<Cand>>,BF:&mut BUF){
for (i,node) in self.nodes[HP].iter().enumerate(){
node.append_cands(input,(HP,i),cands,&mut self.best_score,&mut self.best,BF);
}
}
fn update<'a,I:Iterator<Item=&'a Cand>>(&mut self,input:&In,HP:usize,it:I){
assert!(self.nodes[HP].is_empty());
for cand in it{
let (i,j)=cand.parent;
let node=cand.to_node(input,&self.nodes[i][j]);
self.nodes[HP].push(node);
}
}
}
fn solve(input:&In)->Vec<usize>{
const M:usize=200;
let mut BF=BUF::new();
let mut beam=Beam::new(Node::new(input));
let mut cands=vec![vec![];H as usize+1];
let mut cnt=vec![0;input.I];
for i in (1..=H as usize).rev(){
beam.enum_cands(input,i,&mut cands,&mut BF);
if i==1{
break;
}
cands[i-1].sort_unstable_by_key(|cand|Reverse(O(cand.score)));
cnt.fill(0);
let th=1;
let it=cands[i-1].iter().filter(|cand|cnt[input.id[cand.pos]]<=th && {cnt[input.id[cand.pos]]+=1; true}).take(M);
beam.update(input,i-1,it);
}
eprintln!("score = {}",beam.best_score-2);
let ret=beam.best.to_vec();
ret
}
fn simulate(input:&In,route:&[usize]){
let mut HP=H+2;
let mut juwels=0;
let mut seen=vec![false;input.I];
seen[0]=true;
for (i,p) in route.iter().cloned().enumerate(){
HP-=input.damage[p][i%60].0;
if let Juwel(id)=input.grid[p]{
if !seen[id]{
seen[id]=true;
juwels+=1;
}
}
}
eprintln!("HP = {HP}");
eprintln!("juwel = {juwels}");
}
fn main(){
let input=In::input();
eprintln!("I = {}",input.I);
let ans=solve(&input);
simulate(&input,&ans);
for w in ans.windows(2){
let id=(0..5).find(|i|DX[*i]==w[1]-w[0]).unwrap();
println!("{}",DC[id]);
}
}
///////////////////////////////////
#[allow(unused)]
struct Scanner{
stack:std::str::SplitAsciiWhitespace<'static>
}
#[allow(unused)]
impl Scanner{
fn new()->Self{
use std::io::Read;
let mut tmp=String::new();
std::io::stdin().read_to_string(&mut tmp).unwrap();
Self{stack:Box::leak(tmp.into_boxed_str()).split_ascii_whitespace()}
}
fn read<T:std::str::FromStr>(&mut self)->T{
self.stack.next().unwrap().parse::<T>().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::<T>()))
}
}
macro_rules! input{
($scan:ident, $($rest:tt)*)=>{
input_inner!{$scan,$($rest)*}
};
}
macro_rules! input_inner{
($scan:ident $(,)?)=>{};
($scan:ident, $name:ident:$t:tt $($rest:tt)*)=>{
let $name=read_value!($scan,$t);
input_inner!{$scan $($rest)*}
};
}
macro_rules! read_value{
($scan:ident, ($($t:tt),*))=>{
($(read_value!($scan, $t)),*)
};
($scan:ident, [$t:tt;$len:expr])=>{
(0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
};
($scan:ident, Chars)=>{
read_value!($scan,String).chars().collect::<Vec<char>>()
};
($scan:ident, Usize1)=>{
read_value!($scan,usize)-1
};
($scan:ident, $t:ty)=>{
$scan.read::<$t>()
};
}
use std::collections::*;
use std::cmp::Reverse;
use std::f64::INFINITY;
#[derive(Clone,Copy,PartialEq,Eq,Debug)]
enum Cell{
Empty,
Wall,
Goal,
Juwel(usize),
Fire,
Enemy
}
use Cell::*;
impl Cell{
fn new(c:char,at:&mut usize)->Cell{
match c{
'.'|'S'=>Empty,
'#'=>Wall,
'G'=>Goal,
'K'=>Juwel(0),
'J'=>{*at+=1; Juwel(*at)},
'F'=>Fire,
'E'=>Enemy,
_=>panic!(),
}
}
fn is_through(&self)->bool{
!matches!(*self,Wall|Goal|Enemy)
}
fn is_block(&self)->bool{
matches!(self,Wall|Enemy)
}
}
const N:usize=60;
const N2:usize=(N+2).pow(2);
const H:i64=1500;
fn get_cost(grid:&[Cell],costs:&[f64],start:usize)->Vec<f64>{
let mut que=BinaryHeap::new();
que.push(Reverse(S(0.,start)));
let mut ret=vec![INFINITY;N2];
ret[start]=0.;
while let Some(Reverse(S(cost,pos)))=que.pop(){
for dd in DD{
let np=pos+dd;
if ret[np].is_infinite(){
let nc=if grid[np].is_through(){
cost+costs[np]
}
else{
continue;
};
ret[np]=nc;
que.push(Reverse(S(nc,np)));
}
}
}
ret
}
struct In{
I:usize,
grid:Vec<Cell>,
id:Vec<usize>,
start:usize,
key:usize,
goal:usize,
cost_key:Vec<f64>,
cost_goal:Vec<f64>,
damage:Vec<Vec<(i64,usize)>>,
}
impl In{
fn input()->In{
let mut scan=Scanner::new();
input!{
scan,
n:usize,
D:i64,
h:i64,
igrid:[Chars;n],
M:usize,
ienemy:[(usize,usize,usize);M]
}
assert_eq!((n,h),(N,H));
let mut grid=vec![Wall;N2];
let mut at=0;
let mut start=!0;
let mut key=!0;
let mut goal=!0;
for i in 1..=N{
for j in 1..=N{
let pos=to(i,j);
let c=igrid[i-1][j-1];
grid[pos]=Cell::new(c,&mut at);
if c=='S'{
start=pos;
}
else if c=='K'{
key=pos;
}
else if c=='G'{
goal=pos;
}
}
}
assert!(start!=!0 && key!=!0 && goal!=!0);
let mut enemy=vec![!0;M];
let mut costf=vec![0.;N2];
let mut reach=vec![vec![];N2];
for (id,&(i,j,d)) in ienemy.iter().enumerate(){
enemy[id]=d;
let pos=to(i+1,j+1);
let addf=D as f64/d as f64+1.;
for dd in DD{
let mut np=pos+dd;
while !grid[np].is_block(){
costf[np]+=addf;
reach[np].push(id);
np+=dd;
}
}
}
let mut damage=vec![vec![(0,!0);60];N2];
let mut cost_id=HashMap::new();
let mut at=0;
for i in 1..=N{
for j in 1..=N{
for k in 0..60{
let cost=reach[to(i,j)].iter().map(|id|(k%enemy[*id]==0) as i64).sum::<i64>()*D+1;
damage[to(i,j)][k].0=cost;
if !cost_id.contains_key(&cost){
let res=cost_id.insert(cost,at);
assert!(res.is_none());
at+=1;
}
}
}
}
for i in 1..=N{
for j in 1..=N{
for k in 0..60{
damage[to(i,j)][k].1=cost_id[&damage[to(i,j)][k].0];
}
}
}
assert!(cost_id.len()<=16);
let mut I=0;
let mut id=vec![!0;N2];
for i in 1..=N{
for j in 1..=N{
if let Juwel(idx)=grid[to(i,j)]{
id[to(i,j)]=idx;
I+=1;
}
}
}
In{
cost_key:get_cost(&grid,&costf,key),
cost_goal:get_cost(&grid,&costf,goal),
grid,start,key,goal,
damage,I,id,
}
}
fn cost(&self,pos:usize,key:bool)->f64{
if key{
self.cost_goal[pos]
}
else{
self.cost_goal[self.key]+self.cost_key[pos]
}
}
}
fn to(i:usize,j:usize)->usize{
i*(N+2)+j
}
const DD:[usize;4]=[!0,(N+2).wrapping_neg(),1,N+2];
const DX:[usize;5]=[!0,(N+2).wrapping_neg(),1,N+2,0];
const DC:[&'static str;5]=["M L","M U","M R","M D","S"];
#[derive(PartialEq,PartialOrd)]
struct O<T:PartialEq+PartialOrd>(T);
impl<T:PartialEq+PartialOrd> Eq for O<T>{}
impl<T:PartialEq+PartialOrd> Ord for O<T>{
fn cmp(&self,a:&O<T>)->std::cmp::Ordering{
self.0.partial_cmp(&a.0).unwrap()
}
}
struct S<T:PartialEq+PartialOrd,U>(T,U);
impl<T:PartialEq+PartialOrd,U> PartialEq for S<T,U>{
fn eq(&self,a:&S<T,U>)->bool{
self.0.eq(&a.0)
}
}
impl<T:PartialEq+PartialOrd,U> PartialOrd for S<T,U>{
fn partial_cmp(&self,a:&S<T,U>)->Option<std::cmp::Ordering>{
self.0.partial_cmp(&a.0)
}
}
impl<T:PartialEq+PartialOrd,U> Eq for S<T,U>{}
impl<T:PartialEq+PartialOrd,U> Ord for S<T,U>{
fn cmp(&self,a:&S<T,U>)->std::cmp::Ordering{
self.partial_cmp(a).unwrap()
}
}
use std::rc::Rc;
#[derive(Clone)]
enum List<T>{
Cons(T,Rc<List<T>>),
Nil
}
use List::*;
impl<T:Clone> List<T>{
fn to_vec(&self)->Vec<T>{
let mut ret=vec![];
let mut ptr=self.clone();
while let Cons(v,prev)=ptr{
ret.push(v.clone());
ptr=(*prev).clone();
}
ret.reverse();
ret
}
fn append(&self,new:&[T])->List<T>{
let mut ret=self.clone();
for n in new{
ret=Cons(n.clone(),Rc::new(ret));
}
ret
}
}
fn get_time()->f64{
static mut START:f64=-1.;
let time=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
unsafe{
if START<0.{
START=time;
}
#[cfg(local)]{
(time-START)*1.6
}
#[cfg(not(local))]{
time-START
}
}
}