結果

問題 No.5017 Tool-assisted Shooting
ユーザー rhoorhoo
提出日時 2023-07-26 14:43:09
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,629 ms / 2,000 ms
コード長 12,861 bytes
コンパイル時間 2,710 ms
コンパイル使用メモリ 171,536 KB
実行使用メモリ 24,324 KB
スコア 4,884,965
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-26 14:46:01
合計ジャッジ時間 164,870 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,544 ms
23,196 KB
testcase_01 AC 1,533 ms
23,796 KB
testcase_02 AC 1,423 ms
23,988 KB
testcase_03 AC 1,513 ms
23,568 KB
testcase_04 AC 1,544 ms
23,352 KB
testcase_05 AC 1,477 ms
23,604 KB
testcase_06 AC 1,534 ms
24,192 KB
testcase_07 AC 1,540 ms
23,328 KB
testcase_08 AC 1,494 ms
23,316 KB
testcase_09 AC 1,482 ms
24,144 KB
testcase_10 AC 1,572 ms
23,496 KB
testcase_11 AC 1,470 ms
23,988 KB
testcase_12 AC 1,508 ms
23,604 KB
testcase_13 AC 1,525 ms
23,484 KB
testcase_14 AC 1,549 ms
24,252 KB
testcase_15 AC 1,531 ms
24,036 KB
testcase_16 AC 1,493 ms
23,340 KB
testcase_17 AC 1,591 ms
23,376 KB
testcase_18 AC 1,488 ms
23,916 KB
testcase_19 AC 1,541 ms
23,664 KB
testcase_20 AC 1,514 ms
24,012 KB
testcase_21 AC 1,593 ms
24,156 KB
testcase_22 AC 1,440 ms
23,604 KB
testcase_23 AC 1,410 ms
23,328 KB
testcase_24 AC 1,533 ms
23,496 KB
testcase_25 AC 1,551 ms
24,324 KB
testcase_26 AC 1,495 ms
23,580 KB
testcase_27 AC 1,477 ms
23,604 KB
testcase_28 AC 1,587 ms
23,388 KB
testcase_29 AC 1,403 ms
24,312 KB
testcase_30 AC 1,423 ms
23,328 KB
testcase_31 AC 1,476 ms
23,988 KB
testcase_32 AC 1,501 ms
23,496 KB
testcase_33 AC 1,560 ms
23,916 KB
testcase_34 AC 1,496 ms
24,228 KB
testcase_35 AC 1,505 ms
23,988 KB
testcase_36 AC 1,403 ms
24,012 KB
testcase_37 AC 1,556 ms
24,132 KB
testcase_38 AC 1,497 ms
23,376 KB
testcase_39 AC 1,512 ms
24,288 KB
testcase_40 AC 1,576 ms
23,508 KB
testcase_41 AC 1,503 ms
24,300 KB
testcase_42 AC 1,629 ms
24,252 KB
testcase_43 AC 1,561 ms
24,000 KB
testcase_44 AC 1,545 ms
24,288 KB
testcase_45 AC 1,481 ms
23,328 KB
testcase_46 AC 1,583 ms
23,604 KB
testcase_47 AC 1,446 ms
24,276 KB
testcase_48 AC 1,605 ms
23,352 KB
testcase_49 AC 1,467 ms
23,616 KB
testcase_50 AC 1,499 ms
23,496 KB
testcase_51 AC 1,567 ms
23,508 KB
testcase_52 AC 1,605 ms
24,024 KB
testcase_53 AC 1,540 ms
24,156 KB
testcase_54 AC 1,498 ms
23,340 KB
testcase_55 AC 1,484 ms
24,228 KB
testcase_56 AC 1,559 ms
23,964 KB
testcase_57 AC 1,519 ms
24,000 KB
testcase_58 AC 1,527 ms
23,616 KB
testcase_59 AC 1,563 ms
23,916 KB
testcase_60 AC 1,560 ms
23,364 KB
testcase_61 AC 1,497 ms
23,328 KB
testcase_62 AC 1,550 ms
23,604 KB
testcase_63 AC 1,502 ms
23,916 KB
testcase_64 AC 1,502 ms
24,312 KB
testcase_65 AC 1,581 ms
24,276 KB
testcase_66 AC 1,591 ms
23,340 KB
testcase_67 AC 1,529 ms
23,328 KB
testcase_68 AC 1,492 ms
23,388 KB
testcase_69 AC 1,570 ms
23,304 KB
testcase_70 AC 1,553 ms
23,496 KB
testcase_71 AC 1,498 ms
24,144 KB
testcase_72 AC 1,484 ms
23,340 KB
testcase_73 AC 1,522 ms
23,340 KB
testcase_74 AC 1,508 ms
24,288 KB
testcase_75 AC 1,519 ms
23,796 KB
testcase_76 AC 1,548 ms
23,568 KB
testcase_77 AC 1,572 ms
23,580 KB
testcase_78 AC 1,544 ms
23,976 KB
testcase_79 AC 1,473 ms
23,484 KB
testcase_80 AC 1,598 ms
23,628 KB
testcase_81 AC 1,543 ms
23,580 KB
testcase_82 AC 1,441 ms
24,300 KB
testcase_83 AC 1,483 ms
23,388 KB
testcase_84 AC 1,518 ms
23,496 KB
testcase_85 AC 1,539 ms
23,484 KB
testcase_86 AC 1,566 ms
23,352 KB
testcase_87 AC 1,529 ms
23,784 KB
testcase_88 AC 1,542 ms
23,916 KB
testcase_89 AC 1,576 ms
23,496 KB
testcase_90 AC 1,582 ms
23,976 KB
testcase_91 AC 1,598 ms
23,988 KB
testcase_92 AC 1,445 ms
23,904 KB
testcase_93 AC 1,612 ms
23,580 KB
testcase_94 AC 1,485 ms
23,592 KB
testcase_95 AC 1,587 ms
23,976 KB
testcase_96 AC 1,561 ms
24,012 KB
testcase_97 AC 1,541 ms
23,808 KB
testcase_98 AC 1,580 ms
23,376 KB
testcase_99 AC 1,531 ms
23,364 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case)]


#[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 c0=input.table0[(prog*TABLE as f64).round() as usize];
                let c1=input.table1[(prog*TABLE as f64).round() as usize];
                eval_score+=enemy.hp as f64*c0;
                eval_level+=enemy.power as f64*c1;
            }
        }

        eval_score+eval_level*input.coef[self.turn as usize]
    }

    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 hash0=input.zob[node.pos as usize]+node.power as u64;
            
            let cand=Cand{
                eval_score:node.eval_score(input),
                hash0,
                hash:hash0+hash,
                node,
            };
            cands.push(cand);
        }
    }
}


#[derive(Clone)]
struct Cand{
    node:Node,
    eval_score:f64,
    hash:u64,
    hash0:u64,
}
impl Cand{
    fn to_node(self)->Node{
        self.node
    }
}


const MAX_WIDTH:usize=200;

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 map=NopHashMap::<u64,u8>::default();
    let mut cands=Vec::with_capacity(MAX_WIDTH*3);
    let M=170;
    const A0:f64=45.;
    const A1:f64=30.;

    '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 _ in 0..((A0+(A1-A0)*(IO.turn as f64/TURN as f64)).round() as usize).min(TURN-IO.turn-1){
            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];
            set.clear();
            map.clear();
            let it=cands.iter().filter(|cand|
                cnt[cand.node.pos as usize]<=30
                && !set.contains(&cand.hash)
                && {
                    let e=map.entry(cand.hash0).or_insert(0);
                    if *e<=15{
                        *e+=1;
                        set.insert(cand.hash);
                        cnt[cand.node.pos as usize]+=1;
                        true
                    } else {
                        false
                    }
                }
            ).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;


const TABLE:usize=65536;


struct Input{
    zob:[u64;W],
    coef:[f64;TURN+1],
    enemy:Vec<Vec<Enemy>>,
    idx:Vec<Vec<(usize,usize)>>,
    table0:[f64;TABLE],
    table1:[f64;TABLE],
}
impl Input{
    fn new()->Input{
        let mut coef=[0.;TURN+1];
        for i in 0..=TURN{
            coef[i]=(TURN-i) as f64*5e-4/(i as f64/TURN as f64).powf(2.2);
        }

        let mut table0=[0.;TABLE];
        for i in 0..TABLE{
            table0[i]=(i as f64/TABLE as f64).powf(1.7);
        }
        
        let mut table1=[0.;TABLE];
        for i in 0..TABLE{
            table1[i]=(i as f64/TABLE as f64).powf(0.9);
        }
        
        Input{
            zob:[();W].map(|_|hash()),
            coef,table0,table1,
            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