#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; #[allow(unused_imports)] use std::io::Write; use std::time::SystemTime; pub struct IO(R, std::io::BufWriter); impl IO { pub fn new(r: R, w: W) -> IO { IO(r, std::io::BufWriter::new(w)) } pub fn write(&mut self, s: S) { #[allow(unused_imports)] use std::io::Write; self.1.write(s.to_string().as_bytes()).unwrap(); } pub fn read(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec(&mut self, n: usize) -> Vec { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec { self.read::().chars().collect() } } #[macro_export] macro_rules! mat { ($($e:expr),*) => { Vec::from(vec![$($e),*]) }; ($($e:expr,)*) => { Vec::from(vec![$($e),*]) }; ($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) }; ($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) }; } pub trait SetMinMax { fn setmin(&mut self, v: Self) -> bool; fn setmax(&mut self, v: Self) -> bool; } impl SetMinMax for T where T: PartialOrd, { fn setmin(&mut self, v: T) -> bool { *self > v && { *self = v; true } } fn setmax(&mut self, v: T) -> bool { *self < v && { *self = v; true } } } fn usize_abs(a: usize, b: usize) -> usize { if a > b { a - b } else { b - a } } #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Coord { pub x: isize, pub y: isize, } #[allow(dead_code)] impl Coord { pub fn new(p: (isize, isize)) -> Self { Coord { x: p.0, y: p.1 } } pub fn from_usize_pair(p: (usize, usize)) -> Self { Coord { x: p.0 as isize, y: p.1 as isize, } } pub fn in_field(&self) -> bool { (0 <= self.x && self.x < WIDTH as isize) && (0 <= self.y && self.y < HEIGHT as isize) } // ペアへの変換 pub fn to_pair(&self) -> (isize, isize) { (self.x, self.y) } pub fn to_usize_pair(&self) -> (usize, usize) { (self.x as usize, self.y as usize) } // マンハッタン距離 pub fn distance(&self, that: &Self) -> isize { (self.x - that.x).abs() + (self.y - that.y).abs() } pub fn mk_4dir(&self) -> Vec { let delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]; delta .iter() .map(|&p| self.plus(&Coord::new(p))) .filter(|&pos| pos.in_field()) .collect() } pub fn com_to_delta(com: char) -> Self { match com { 'U' => Coord::new((0, -1)), 'D' => Coord::new((0, 1)), 'L' => Coord::new((-1, 0)), 'R' => Coord::new((1, 0)), _ => unreachable!(), } } // 四則演算 pub fn plus(&self, that: &Self) -> Self { Coord::new((self.x + that.x, self.y + that.y)) } pub fn minus(&self, that: &Self) -> Self { Coord::new((self.x - that.x, self.y - that.y)) } pub fn access_matrix<'a, T>(&'a self, mat: &'a Vec>) -> &'a T { &mat[self.y as usize][self.x as usize] } pub fn set_matrix(&self, mat: &mut Vec>, e: T) { mat[self.y as usize][self.x as usize] = e; } } // println!("{}") での表示内容 impl std::fmt::Display for Coord { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "({}, {})", self.x, self.y)?; Ok(()) } } // println!("{:?}") での表示内容 impl std::fmt::Debug for Coord { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "({}, {})", self.x, self.y)?; Ok(()) } } const WIDTH: usize = 25; const HEIGHT: usize = 60; const ENEMY_NUM_MAX: usize = 25; const MAX_TURN: usize = 1_000; #[derive(Clone, Copy, Debug, PartialEq)] enum Command { Left, Right, Stay, } impl Command { fn to_string(&self) -> &str { match self { Command::Left => "L", Command::Right => "R", Command::Stay => "S", } } fn list() -> Vec { vec![Command::Left, Command::Right, Command::Stay] } fn move_num(&self) -> usize { match self { Command::Left => WIDTH - 1, Command::Right => 1, Command::Stay => 0, } } } #[derive(Clone, Copy, Debug)] struct Enemy { hp: usize, // HP (自機レベルが1ターンの与ダメージ。倒すとHP分のスコアが得られる。) power: usize, // パワー (100ごとに自機のレベルが1上がる) x: usize, // x座標 score: usize, // 倒したときのスコア } impl Enemy { fn new(hp: usize, power: usize, x: usize) -> Self { Self { hp, power, x, score: hp, } } } #[allow(dead_code)] struct Input { n: usize, enemies: Vec, } impl Input { fn new(n: usize, sc: &mut IO, std::io::StdoutLock<'_>>) -> Self { let mut enemies = vec![]; for _ in 0..n { let v = (0..3).map(|_| sc.read::()).collect::>(); let e = Enemy::new(v[0], v[1], v[2]); enemies.push(e); } Self { n, enemies } } } #[derive(Clone, Debug)] struct State { me: usize, // 自機のx座標 exp: usize, // 破壊敵機のパワーの通算。100ごとにレベルアップ。 turn: usize, // 現在のターン数 field: Vec>>, score: usize, } impl State { fn new() -> Self { Self { me: 12, exp: 0, turn: 0, field: mat![None; HEIGHT; WIDTH], score: 0, } } fn get_level(&self) -> usize { 1 + self.exp / 100 } // inputを反映させる更新 // 1. フィールドに存在する全ての敵機が下に1マス移動する。フィールド外に移動した敵機は消滅する。 // 2. 一番上の行に新たな敵機が出現する。出現確率は後述のように列ごとに定められている。 // => isLive fn update_by_input(&mut self, input: &Input) -> bool { let mut new_row = vec![None; WIDTH]; for e in input.enemies.iter() { new_row[e.x] = Some(e.clone()); } self.field.remove(0); self.field.push(new_row); if self.field[0][self.me].is_some() { eprintln!("Game Over. ターン: {}, スコア: {}", self.turn, self.score); return false; } true } // シミュレーション用 fn update_by_empty_input(&mut self) -> bool { let new_row = vec![None; WIDTH]; self.field.remove(0); self.field.push(new_row); if self.field[0][self.me].is_some() { return false; } true } // 3. 自機を左右いずれかに1マス移動、またはその場にとどまる。 // 4. 自機と同じ列に存在する敵機の中で自機に一番近い敵機を自動で攻撃する。 // => isLive fn update_by_cmd(&mut self, cmd: &Command) -> bool { // 移動 self.me = (self.me + cmd.move_num()) % WIDTH; // 射撃 let x = self.me; if let Some(ene_pos) = self.find_nearest_on_col(x) { let (_, y) = ene_pos.to_usize_pair(); let mut enemy = self.field[y][x].clone().unwrap(); if enemy.hp <= self.get_level() { self.score += enemy.score; self.exp += enemy.power; self.field[y][x] = None; } else { enemy.hp -= self.get_level(); self.field[y][x] = Some(enemy) } } if self.field[0][self.me].is_some() { return false; } true } // 指定したカラムの一番下に居る敵機の座標を返す fn find_nearest_on_col(&self, x: usize) -> Option { let mut res = None; for y in 1..HEIGHT { if self.field[y][x].is_some() { res = Some(Coord::from_usize_pair((x, y))); break; } } res } /* user define */ // 最速で倒せるx座標を返す fn search_fastest_break(&self, excludes: &Vec) -> Option { let mut row = vec![4242; WIDTH]; let level = self.get_level(); let init_x = self.me; if let Some(enemy_pos) = self.find_nearest_on_col(init_x) { let enemy = enemy_pos.access_matrix(&self.field).unwrap(); // 所要ターン数 let turn = (enemy.hp + level - 1) / level; if turn <= enemy_pos.y as usize { row[init_x] = turn; } } for i in 1..=WIDTH / 2 { // [右移動, 左移動] for x in [(init_x + i) % WIDTH, (init_x + WIDTH - i) % WIDTH] { if excludes.contains(&x) { continue; } if let Some(enemy_pos) = self.find_nearest_on_col(x) { let enemy = enemy_pos.access_matrix(&self.field).unwrap(); // 所要ターン数 ((i-1)は移動分) let turn = (enemy.hp + level - 1) / level + (i - 1); if turn <= enemy_pos.y as usize { row[x] = turn; } } } } let mut res = None; let mut best = 4242; for x in 0..WIDTH { if row[x] < best { res = Some(x); best = row[x]; } } res } } fn main() { let system_time = SystemTime::now(); let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock()); let mut st = State::new(); for turn in 1..=MAX_TURN { st.turn = turn; /* input & update */ let n: isize = sc.read(); if n == -1 { break; } let n = n as usize; let input = Input::new(n, &mut sc); st.update_by_input(&input); /* solve */ let mut cmd = Command::Stay; if turn >= 976 { const BEAM_WIDTH: usize = 50; let mut q = vec![(st.clone(), vec![])]; for _ in turn..=1000 { let mut next_q = vec![]; for (next_st, coms) in q { for cmd in Command::list() { let mut next_st = next_st.clone(); if next_st.update_by_cmd(&cmd) { if next_st.update_by_empty_input() { let mut next_coms = coms.clone(); next_coms.push(cmd); next_q.push((next_st, next_coms)); } } } } // next_qをソートして絞り込む next_q.sort_by_key(|(st, _)| st.score); next_q.reverse(); q = next_q[..BEAM_WIDTH.min(next_q.len())].to_vec(); } cmd = q[0].1[0]; } else { let mut excledes = vec![]; loop { if let Some(x) = st.search_fastest_break(&excledes) { // 自機ポジションを原点とするx座標 let offset = (x + WIDTH - st.me) % WIDTH; if offset == 0 { cmd = Command::Stay; } else if offset <= WIDTH / 2 { cmd = Command::Right; } else { cmd = Command::Left; } // ダメだったらexcludesに追加 if !can_move(st.clone(), x, &cmd) { excledes.push(x); } else { break; } } else { break; } } // stayして死ぬなら右に移動 if let Some(enemy) = st.field[1][st.me as usize] { if cmd == Command::Stay { if enemy.hp > st.get_level() { cmd = Command::Right; } } } } /* output & update */ println!("{}", cmd.to_string()); st.update_by_cmd(&cmd); // eprintln!("score {}: {}", turn, st.score); } eprintln!("{}ms", system_time.elapsed().unwrap().as_millis()); eprintln!("score: {}", st.score); } fn can_move(mut st: State, x: usize, dir: &Command) -> bool { if *dir == Command::Stay { return true; } while st.me != x { if !st.update_by_cmd(dir) { return false; } if !st.update_by_empty_input() { return false; } } true }