結果

問題 No.5017 Tool-assisted Shooting
ユーザー rhoo
提出日時 2023-07-19 22:50:54
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,971 ms / 2,000 ms
コード長 12,124 bytes
コンパイル時間 5,285 ms
コンパイル使用メモリ 171,240 KB
実行使用メモリ 24,420 KB
スコア 4,825,290
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-19 22:53:59
合計ジャッジ時間 68,156 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(non_snake_case)]
static mut R:usize=0;
#[derive(Clone,PartialEq)]
struct Node{
    first:u8,
    pos:u8,
    power:u32,
    score:u32,
    turn:u16,
    idx:[u8;W],
    damage:[u16;W],
}
impl Node{
    fn next_step(&mut self,input:&Input){
        for &(pos,_) in &input.idx[self.turn as usize]{
            if let Some(enemy)=input.get(pos,self.idx[pos as usize] as usize){
                if enemy.height<=self.turn as usize{
                    self.damage[pos]=0;
                    self.idx[pos]+=1;
                }
            }
        }
    }
    fn isok(&self,input:&Input,pos:usize,turn:usize)->bool{
        input.get(pos,self.idx[pos] as usize).map_or(true,|e|e.height-1!=turn)
    }
    fn apply(&mut self,input:&Input,op:u8)->bool{
        self.pos=self.pos.apply(op);
        if !self.isok(input,self.pos as usize,self.turn as usize){
            return false;
        }
        let level=self.power/100;
        let pos=self.pos as usize;
        if let Some(enemy)=input.get(pos,self.idx[pos] as usize){
            self.damage[pos]+=level as u16;
            if self.damage[pos] as u32>=enemy.hp{
                self.damage[pos]=0;
                self.idx[pos]+=1;
                self.score+=enemy.hp;
                self.power+=enemy.power;
            }
        }
        if !self.isok(input,self.pos as usize,self.turn as usize+1){
            return false;
        }
        self.turn+=1;
        true
    }
    fn eval_score(&self,input:&Input)->f64{
        let mut eval_score=self.score as f64;
        let mut eval_level=self.power as f64;
        let pos=self.pos as usize;
        if let Some(enemy)=input.get(pos,self.idx[pos] as usize){
            let height=enemy.height-self.turn as usize+3;
            let prog=self.damage[pos] as f64/enemy.hp as f64;
            if self.power/100*height as u32>=enemy.hp-self.damage[pos] as u32{
                let c=prog*prog;
                eval_score+=enemy.hp as f64*c;
                eval_level+=enemy.power as f64*c;
            }
        }
        eval_score+eval_level*input.coef[self.turn as usize]+(rnd::next()%unsafe{R}) as f64
    }
    fn append_cands(&self,input:&Input,cands:&mut Vec<Cand>){
        let get_hash=|node:&Node,pos:usize|->u64{
            input.get(pos,node.idx[pos] as usize).map_or(0,|e|e.hash*node.damage[pos] as u64)
        };
        let hash=(0..W).map(|i|get_hash(self,i)).sum::<u64>();
        for op in [!0,0,1]{
            let mut node=self.clone();
            let mut hash=hash;
            hash-=get_hash(&node,node.pos.apply(op) as usize);
            if !node.apply(input,op){
                continue;
            }
            hash+=get_hash(&node,node.pos as usize);
            let cand=Cand{
                eval_score:node.eval_score(input),
                hash:(hash^input.zob[node.pos as usize])+node.power as u64,
                node,
            };
            cands.push(cand);
        }
    }
}
#[derive(Clone)]
struct Cand{
    node:Node,
    eval_score:f64,
    hash:u64,
}
impl Cand{
    fn to_node(self)->Node{
        self.node
    }
}
const MAX_WIDTH:usize=400;
struct BeamSearch{
    nodes:Vec<Node>,
}
impl BeamSearch{
    fn new()->BeamSearch{
        BeamSearch{
            nodes:Vec::with_capacity(MAX_WIDTH),
        }
    }
    fn enum_cands(&self,input:&Input,cands:&mut Vec<Cand>){
        for node in &self.nodes{
            node.append_cands(input,cands);
        }
    }
    fn update<I:Iterator<Item=Cand>>(&mut self,input:&Input,cands:I){
        self.nodes.clear();
        for cand in cands{
            let mut node=cand.to_node();
            node.next_step(input);
            self.nodes.push(node);
        }
    }
}
fn solve(IO:&mut IO){
    let mut solver=BeamSearch::new();
    let mut set=NopHashSet::<u64>::default();
    let mut cands=Vec::with_capacity(MAX_WIDTH*3);
    let M=230;
    'a: loop{
        IO.read();
        solver.nodes.clear();
        
        for op in [!0,0,1]{
            let mut node=IO.state.clone();
            if !node.apply(&IO.input,op){
                continue;
            }
            node.first=op;
            solver.nodes.push(node);
        }
        for t in 0..30.min(TURN-IO.turn-1){
            const R0:f64=10.;
            const R1:f64=15.;
            unsafe{
                R=(R0+(R1-R0)*((IO.turn+t+1) as f64/TURN as f64)).round() as usize;
            }
            
            cands.clear();
            solver.enum_cands(&IO.input,&mut cands);
            assert!(!cands.is_empty());
            cands.sort_unstable_by_key(|cand|Reverse(O(cand.eval_score)));
            
            let mut cnt=[0;W];
            let th=M/5;
            set.clear();
            let it=cands.iter().filter(|cand|
                cnt[cand.node.pos as usize]<=th
                && set.insert(cand.hash)
                && {
                    cnt[cand.node.pos as usize]+=1;
                    true
                }
            ).take(M).cloned();
            solver.update(&IO.input,it);
            let op=solver.nodes[0].first;
            if solver.nodes.iter().all(|node|node.first==op){
                IO.write(op);
                continue 'a;
            }
        }
        IO.write(solver.nodes[0].first);
    }
}
fn main(){
    let mut IO=IO::new();
    solve(&mut IO)
}
#[derive(Clone,Copy)]
struct Enemy{
    hash:u64,
    hp:u32,
    power:u32,
    height:usize,
}
use std::cmp::*;
const TURN:usize=1000;
const H:usize=60;
const W:usize=25;
struct Input{
    zob:[u64;W],
    coef:[f64;TURN+1],
    enemy:Vec<Vec<Enemy>>,
    idx:Vec<Vec<(usize,usize)>>,
}
impl Input{
    fn new()->Input{
        let mut coef=[0.;TURN+1];
        for i in 0..=TURN{
            coef[i]=(TURN-i) as f64*7e-4/(i as f64/TURN as f64).powf(2.2);
        }
        Input{
            zob:[();W].map(|_|hash()),
            coef,
            enemy:vec![vec![];W],
            idx:vec![vec![];TURN+H],
        }
    }
    fn get(&self,pos:usize,idx:usize)->Option<&Enemy>{
        self.enemy[pos].get(idx)
    }
}
struct IO{
    scan:Scanner,
    turn:usize,
    state:Node,
    input:Input,
}
impl IO{
    fn new()->IO{
        get_time();
        #[allow(unused_mut)]
        let mut scan=Scanner::new();
        #[cfg(local)]{
            input!{
                scan,
                _a:[usize;W],
            }
        }
        let state=Node{
            first:0,
            pos:12,
            power:100,
            score:0,
            turn:0,
            idx:[0;W],
            damage:[0;W],
        };
        IO{
            scan,state,
            input:Input::new(),
            turn:0,
        }
    }
    fn exit(&self){
        eprintln!("score = {}",self.state.score);
        eprintln!("timer = {:.2}",unsafe{TIME});
        eprintln!("time = {:.2}",get_time());
        std::process::exit(0);
    }
    fn read(&mut self){
        input!{
            self.scan,
            n:i64,
        }
        if n==-1{
            self.exit();
        }
        input!{
            self.scan,
            enemy:[(u32,u32,usize);n],
        }
        for (hp,power,pos) in enemy{
            self.input.idx[self.turn+H].push((pos,self.input.enemy[pos].len()));
            let enemy=Enemy{
                hp,power,
                height:self.turn+H,
                hash:hash(),
            };
            self.input.enemy[pos].push(enemy);
        }
    }
    fn write(&mut self,op:u8){
        match op{
            u8::MAX=>println!("L"),
            0=>println!("S"),
            1=>println!("R"),
            _=>panic!(),
        }
        
        let f=self.state.apply(&self.input,op);
        assert!(f,"敵に当たってるよ");
        self.state.next_step(&self.input);
        self.turn+=1;
        if self.turn==TURN{
            self.exit();
        }
    }
}
fn hash()->u64{
    (rnd::next()+rnd::next()) as u64
}
trait My{
    fn apply(self,op:u8)->u8;
}
impl My for u8{
    fn apply(self,op:u8)->u8{
        (self+op+W as u8)%W as u8
    }
}
#[macro_export]#[cfg(not(local))]macro_rules! eprint{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! eprintln{($($_:tt)*)=>{}}
#[allow(unused)]
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
        }
    }
}
#[macro_export]
macro_rules! timer{
    ()=>{
        let _timer=Timer(get_time());
    }
}
static mut TIME:f64=0.;
#[allow(unused)]
fn time_sum()->f64{
    unsafe{ TIME }
}
struct Timer(f64);
impl Drop for Timer{
    fn drop(&mut self){
        unsafe{
            TIME+=get_time()-self.0
        }
    }
}
#[allow(unused)]
mod rnd {
    static mut S:usize=88172645463325252;
    
    pub fn next()->usize{
        unsafe{
            S^=S<<13;
            S^=S>>7;
            S^=S<<17;
            S
        }
    }
    pub fn nextf()->f64{
        unsafe{
            std::mem::transmute::<u64,f64>((0x3ff0000000000000|next()&0xfffffffffffff) as u64)-1.
        }
    }
    pub fn range(a:usize,b:usize)->usize{
        next()%(b-a)+a
    }
}
struct Scanner{
    stack:std::str::SplitAsciiWhitespace<'static>
}
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>()))
    // }
    
    // インタラクティブ用
    fn new()->Self{
        Self{stack:"".split_ascii_whitespace()}
    }
    #[track_caller]
    fn read<T:std::str::FromStr>(&mut self)->T{
        loop{
            if let Some(v)=self.stack.next(){
                return v.parse::<T>().unwrap_or_else(|_|panic!("{}: parse error",std::any::type_name::<T>()));
            }
            let mut tmp=String::new();
            std::io::stdin().read_line(&mut tmp).unwrap();
            assert!(!tmp.is_empty());
            self.stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace();
        }
    }
}
#[macro_export]
macro_rules! input{
    ($scan:expr $(,)?)=>{};
    ($scan:expr, mut $name:ident:$t:tt $($rest:tt)*)=>{
        let mut $name=read_value!($scan,$t);
        input!{$scan $($rest)*}
    };
    ($scan:expr, $name:ident:$t:tt $($rest:tt)*)=>{
        let $name=read_value!($scan,$t);
        input!{$scan $($rest)*}
    };
}
#[macro_export]
macro_rules! read_value{
    ($scan:expr, ($($t:tt),*))=>{
        ($(read_value!($scan, $t)),*)
    };
    ($scan:expr, [$t:tt;$len:expr])=>{
        (0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
    };
    ($scan:expr, [$t:tt])=>{
        (0..$scan.read()).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
    };
    ($scan:expr, Chars)=>{
        read_value!($scan,String).chars().collect::<Vec<char>>()
    };
    ($scan:expr, Usize1)=>{
        read_value!($scan,usize)-1
    };
    ($scan:expr, $t:ty)=>{
        $scan.read::<$t>()
    };
}
#[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()
    }
}
use std::collections::{HashMap,HashSet};
use core::hash::BuildHasherDefault;
use core::hash::Hasher;
#[derive(Default)]
pub struct NopHasher{
    hash:u64,
}
impl Hasher for NopHasher{
    fn write(&mut self,_:&[u8]){
        panic!();
    }
    #[inline]
    fn write_u64(&mut self,n:u64){
        self.hash=n;
    }
    #[inline]
    fn finish(&self)->u64{
        self.hash
    }
}
pub type NopHashMap<K,V>=HashMap<K,V,BuildHasherDefault<NopHasher>>;
pub type NopHashSet<V>=HashSet<V,BuildHasherDefault<NopHasher>>;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0