結果

問題 No.5017 Tool-assisted Shooting
ユーザー rhoorhoo
提出日時 2023-07-19 22:50:54
言語 Rust
(1.77.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,710 ms
23,400 KB
testcase_01 AC 1,730 ms
24,336 KB
testcase_02 AC 1,632 ms
24,252 KB
testcase_03 AC 1,702 ms
23,604 KB
testcase_04 AC 1,732 ms
23,400 KB
testcase_05 AC 1,710 ms
24,012 KB
testcase_06 AC 1,662 ms
24,048 KB
testcase_07 AC 1,674 ms
24,240 KB
testcase_08 AC 1,675 ms
23,472 KB
testcase_09 AC 1,706 ms
23,952 KB
testcase_10 AC 1,736 ms
24,072 KB
testcase_11 AC 1,609 ms
23,568 KB
testcase_12 AC 1,709 ms
23,412 KB
testcase_13 AC 1,679 ms
23,964 KB
testcase_14 AC 1,736 ms
23,616 KB
testcase_15 AC 1,735 ms
23,400 KB
testcase_16 AC 1,652 ms
24,012 KB
testcase_17 AC 1,712 ms
23,592 KB
testcase_18 AC 1,712 ms
24,060 KB
testcase_19 AC 1,712 ms
23,820 KB
testcase_20 AC 1,736 ms
24,132 KB
testcase_21 AC 1,729 ms
23,964 KB
testcase_22 AC 1,634 ms
23,808 KB
testcase_23 AC 1,712 ms
23,424 KB
testcase_24 AC 1,718 ms
24,084 KB
testcase_25 AC 1,774 ms
24,288 KB
testcase_26 AC 1,697 ms
23,556 KB
testcase_27 AC 1,693 ms
23,580 KB
testcase_28 AC 1,710 ms
23,388 KB
testcase_29 AC 1,664 ms
24,300 KB
testcase_30 AC 1,644 ms
23,412 KB
testcase_31 AC 1,678 ms
24,408 KB
testcase_32 AC 1,675 ms
24,216 KB
testcase_33 AC 1,766 ms
23,964 KB
testcase_34 AC 1,677 ms
24,036 KB
testcase_35 AC 1,737 ms
24,324 KB
testcase_36 AC 1,650 ms
23,424 KB
testcase_37 AC 1,709 ms
24,252 KB
testcase_38 AC 1,686 ms
24,300 KB
testcase_39 AC 1,851 ms
23,424 KB
testcase_40 AC 1,746 ms
23,472 KB
testcase_41 AC 1,672 ms
23,568 KB
testcase_42 AC 1,751 ms
24,264 KB
testcase_43 AC 1,739 ms
23,460 KB
testcase_44 AC 1,673 ms
23,808 KB
testcase_45 AC 1,681 ms
23,568 KB
testcase_46 AC 1,759 ms
24,300 KB
testcase_47 AC 1,741 ms
24,024 KB
testcase_48 AC 1,748 ms
23,604 KB
testcase_49 AC 1,703 ms
23,604 KB
testcase_50 AC 1,720 ms
23,952 KB
testcase_51 AC 1,694 ms
23,580 KB
testcase_52 AC 1,709 ms
23,616 KB
testcase_53 AC 1,742 ms
23,580 KB
testcase_54 AC 1,696 ms
24,000 KB
testcase_55 AC 1,701 ms
23,964 KB
testcase_56 AC 1,707 ms
24,288 KB
testcase_57 AC 1,671 ms
24,324 KB
testcase_58 AC 1,691 ms
24,024 KB
testcase_59 AC 1,695 ms
23,820 KB
testcase_60 AC 1,692 ms
23,616 KB
testcase_61 AC 1,666 ms
23,472 KB
testcase_62 AC 1,675 ms
24,408 KB
testcase_63 AC 1,744 ms
23,808 KB
testcase_64 AC 1,768 ms
23,904 KB
testcase_65 AC 1,744 ms
24,408 KB
testcase_66 AC 1,704 ms
23,400 KB
testcase_67 AC 1,651 ms
23,604 KB
testcase_68 AC 1,688 ms
23,604 KB
testcase_69 AC 1,671 ms
23,400 KB
testcase_70 AC 1,703 ms
23,376 KB
testcase_71 AC 1,705 ms
23,868 KB
testcase_72 AC 1,656 ms
24,396 KB
testcase_73 AC 1,971 ms
24,396 KB
testcase_74 AC 1,614 ms
23,592 KB
testcase_75 AC 1,702 ms
24,276 KB
testcase_76 AC 1,759 ms
23,568 KB
testcase_77 AC 1,753 ms
23,964 KB
testcase_78 AC 1,769 ms
24,264 KB
testcase_79 AC 1,692 ms
23,400 KB
testcase_80 AC 1,751 ms
23,964 KB
testcase_81 AC 1,724 ms
23,964 KB
testcase_82 AC 1,690 ms
24,408 KB
testcase_83 AC 1,712 ms
23,604 KB
testcase_84 AC 1,694 ms
24,264 KB
testcase_85 AC 1,689 ms
23,796 KB
testcase_86 AC 1,779 ms
24,288 KB
testcase_87 AC 1,667 ms
24,312 KB
testcase_88 AC 1,726 ms
23,424 KB
testcase_89 AC 1,709 ms
24,276 KB
testcase_90 AC 1,760 ms
24,180 KB
testcase_91 AC 1,768 ms
24,216 KB
testcase_92 AC 1,664 ms
24,000 KB
testcase_93 AC 1,737 ms
23,988 KB
testcase_94 AC 1,619 ms
23,952 KB
testcase_95 AC 1,692 ms
24,420 KB
testcase_96 AC 1,702 ms
24,420 KB
testcase_97 AC 1,724 ms
24,240 KB
testcase_98 AC 1,732 ms
24,276 KB
testcase_99 AC 1,700 ms
23,964 KB
権限があれば一括ダウンロードができます

ソースコード

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>>;
0