#![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){ 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::(); 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, } impl BeamSearch{ fn new()->BeamSearch{ BeamSearch{ nodes:Vec::with_capacity(MAX_WIDTH), } } fn enum_cands(&self,input:&Input,cands:&mut Vec){ for node in &self.nodes{ node.append_cands(input,cands); } } fn update>(&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::::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>, idx:Vec>, } 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::((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(&mut self)->T{ // self.stack.next().unwrap().parse::().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::())) // } // インタラクティブ用 fn new()->Self{ Self{stack:"".split_ascii_whitespace()} } #[track_caller] fn read(&mut self)->T{ loop{ if let Some(v)=self.stack.next(){ return v.parse::().unwrap_or_else(|_|panic!("{}: parse error",std::any::type_name::())); } 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::>() }; ($scan:expr, [$t:tt])=>{ (0..$scan.read()).map(|_|read_value!($scan,$t)).collect::>() }; ($scan:expr, Chars)=>{ read_value!($scan,String).chars().collect::>() }; ($scan:expr, Usize1)=>{ read_value!($scan,usize)-1 }; ($scan:expr, $t:ty)=>{ $scan.read::<$t>() }; } #[derive(PartialEq,PartialOrd)] struct O(T); impl Eq for O{} impl Ord for O{ fn cmp(&self,a:&O)->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=HashMap>; pub type NopHashSet=HashSet>;