//-------------------------------------------------------------------------------- #[allow(unused_macros)] macro_rules! debug { ($($a:expr),*) => { #[cfg(feature = "single_testcase")] { eprint!("[line:{}] ", line!()); eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*); } } } fn get_time() -> f64 { static mut STIME: f64 = -1.0; let t = std::time::SystemTime::now() .duration_since(std::time::UNIX_EPOCH) .unwrap(); let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9; unsafe { if STIME < 0.0 { STIME = ms; } ms - STIME } } //-------------------------------------------------------------------------------- // https://atcoder.jp/contests/intro-heuristics/submissions/14832097 // let D = read!(usize); // let c = read!([i64]); // let s = read!([i64]; D); // let (n, m) = read!(i32, i32); #[allow(dead_code)] fn readln() -> String { let mut line = String::new(); ::std::io::stdin() .read_line(&mut line) .unwrap_or_else(|e| panic!("{}", e)); line } #[allow(unused_macros)] macro_rules! read { ($($t:tt),*; $n:expr) => {{ let stdin = ::std::io::stdin(); let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| { let line = line.unwrap(); let mut it = line.split_whitespace(); _read!(it; $($t),*) }).collect::>(); ret }}; ($($t:tt),*) => {{ let line = readln(); let mut it = line.split_whitespace(); _read!(it; $($t),*) }}; } macro_rules! _read { ($it:ident; [char]) => { _read!($it; String).chars().collect::>() }; ($it:ident; [u8]) => { Vec::from(_read!($it; String).into_bytes()) }; ($it:ident; usize1) => { $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::().unwrap_or_else(|e| panic!("{}", e)) - 1 }; ($it:ident; [usize1]) => { $it.map(|s| s.parse::().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::>() }; ($it:ident; [$t:ty]) => { $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::>() }; ($it:ident; $t:ty) => { $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e)) }; ($it:ident; $($t:tt),+) => { ($(_read!($it; $t)),*) }; } //-------------------------------------------------------------------------------- // https://atcoder.jp/contests/hokudai-hitachi2017-1/submissions/1797182 // u32 -> usize pub struct XorShift { pub x: [usize; 4], } impl XorShift { pub fn new(mut seed: usize) -> XorShift { let mut x = [0; 4]; for i in 0..4 { seed = 1812433253usize .wrapping_mul(seed ^ (seed >> 30)) .wrapping_add(i as usize); x[i] = seed; } XorShift { x } } pub fn next_usize(&mut self) -> usize { let t = self.x[0] ^ (self.x[0] << 11); for i in 0..3 { self.x[i] = self.x[i + 1] } self.x[3] = self.x[3] ^ (self.x[3] >> 19) ^ t ^ (t >> 8); self.x[3] } /// [0, n) pub fn next(&mut self, n: usize) -> usize { loop { let t = self.next_usize(); let r = t % n; if (t - r).checked_add(n).is_some() { return r; } } } pub fn shuffle(&mut self, a: &mut [T]) { for i in 0..a.len() { let j = i + self.next(a.len() - i) as usize; a.swap(i, j); } } } //-------------------------------------------------------------------------------- const SEED: u32 = 890482; const TIME_LIMIT: f64 = 1.9; const INF: usize = 1_000_000_000; const NUM_TURNS: usize = 1000; const X: usize = 25; const Y: usize = 60; #[derive(Debug, Clone, Copy, PartialEq, Eq)] struct Enemy { x: usize, y: usize, init_hp: i32, hp: i32, power: i32, } fn read_probs() -> Vec { let probs = read!([i8]); probs } fn read_input() -> Option> { let n = read!(i8); if n == -1 { None } else { let mut enemys = vec![]; for _ in 0..n { let (init_hp, power, x) = read!(i32, i32, usize); enemys.push(Enemy { x, y: Y - 1, init_hp, hp: init_hp, power}); } Some(enemys) } } #[derive(Debug)] struct Player { x: usize, y: usize, score: i32, power: i32, level: i32, } #[derive(Debug)] struct State { board: [[Option; X]; Y], player: Player, } impl State { fn new() -> Self { let board = [[None; X]; Y]; let player = Player { x: X / 2, y: 0, score: 0, power: 0, level: 1 }; Self { board, player } } fn update_before(&mut self, enemys: Vec) -> bool { // 敵機の更新 for y in 0..Y - 1 { for x in 0..X { self.board[y][x] = self.board[y+1][x]; if let Some(enemy) = &mut self.board[y][x] { enemy.y -= 1; } } } for x in 0..X { self.board[Y-1][x] = None; } for enemy in enemys.into_iter() { self.board[Y-1][enemy.x] = Some(enemy); } if let Some(_enemy) = self.board[self.player.y][self.player.x] { false } else { true } } fn update_after(&mut self, command: char) { // 移動 if command == 'L' { if self.player.x == 0 { self.player.x = X - 1; } else { self.player.x -= 1; } } else if command == 'R' { if self.player.x == X - 1 { self.player.x = 0; } else { self.player.x += 1; } } else if command == 'S' { // Stay } else { unreachable!(); } // 攻撃 for y in 1..Y { if let Some(enemy) = &mut self.board[y][self.player.x] { debug!(enemy); enemy.hp -= self.player.level; if enemy.hp <= 0 { // 破壊した self.player.score += enemy.init_hp; self.player.power += enemy.power; self.player.level = 1 + self.player.power / 100; self.board[y][self.player.x] = None; } break; } } } } fn solve(state: &State, turn: usize) -> char { let mut max_eval_score = 0.0; let mut max_command = 'S'; let mut max_enemy = None; for x in 0..X { let mut arrive_dturn = INF; let mut command = 'S'; if x == state.player.x { arrive_dturn = 0; command = 'S'; } else { let mut min_dturn = INF; let mut min_command = 'S'; for &dx in [!0, 1].iter() { let mut now_x = state.player.x; let mut cmd = 'S'; for dturn in 1..=NUM_TURNS - turn { let next_x = now_x.wrapping_add(dx) % X; let no_conflict_0 = dturn - 1 >= Y || state.board[dturn - 1][next_x] == None; let no_conflict_1 = dturn >= Y || (state.board[dturn][next_x] == None || state.board[dturn][next_x].unwrap().hp <= state.player.level); if no_conflict_0 && no_conflict_1 { now_x = next_x; } if dturn == 1 { if no_conflict_0 && no_conflict_1 { cmd = if dx == !0 { 'L' } else { 'R' }; } else { cmd = 'S'; } } if now_x == x { if dturn < min_dturn { min_dturn = dturn; min_command = cmd; } break; } } } if min_dturn != INF { arrive_dturn = min_dturn; command = min_command; } } // debug!(x, arrive_dturn, command); if arrive_dturn < Y { let t = turn as f64 / NUM_TURNS as f64; for y in arrive_dturn..Y { if let Some(enemy) = state.board[y][x] { if (enemy.hp + state.player.level - 1) / state.player.level <= (y - arrive_dturn) as i32 { // 破壊できる let destroy_dturn = arrive_dturn as i32 + (enemy.hp + state.player.level - 1) / state.player.level; let eval_score = (t * enemy.init_hp as f64 + (1.0 - t) * (enemy.power * enemy.power) as f64 / 10000.0) / destroy_dturn as f64; if eval_score > max_eval_score { max_eval_score = eval_score; max_command = command; max_enemy = Some(enemy); } } break; } } } } if let Some(_enemy) = state.board[1][state.player.x] { let lx = state.player.x.wrapping_add(!0) % X; if state.board[0][lx] == None && state.board[1][lx] == None { max_command = 'L'; } else { max_command = 'R'; } } debug!(max_eval_score, max_command, max_enemy); max_command } fn main() { get_time(); #[cfg(feature = "single_testcase")] read_probs(); let mut state = State::new(); for turn in 1..=NUM_TURNS { // if turn == 5 { // break; // } // debug!(state.board[2]); // debug!(state.board[1]); // debug!(state.board[0]); let enemys = read_input(); match enemys { Some(enemys) => { let ok = state.update_before(enemys); if !ok { debug!(turn); break; } debug!(turn, state.player); debug!(state.board[0]); debug!(state.board[1]); let command = solve(&state, turn); eprintln!("{}", command); println!("{}", command); state.update_after(command); }, None => break, } } debug!(state.player.score); eprintln!("time_elapsed: {:.3}", get_time()); }