use std::{collections::VecDeque, io, io::Write}; const WIDTH: usize = 25; const HEIGHT: usize = 60; const CENTER: usize = WIDTH / 2; #[allow(dead_code)] const MAX_TURN: usize = 1000; const TARGET_LEVEL: usize = 250; // 決め打ち const INF: usize = 1 << 60; // codingameから拝借 macro_rules! parse_input { ($x:expr, $t:ident) => { $x.trim().parse::<$t>().unwrap() }; } fn main() { let mut player = Player::new(); let mut enemies = vec![VecDeque::new(); WIDTH]; let mut init_hp_sums = vec![0; WIDTH]; let mut enemies_score_sums = vec![0.; WIDTH]; let mut turn = 1; while let Some(new_enemies) = read_input() { preprocess(&mut enemies, new_enemies, &mut init_hp_sums); let target_x = greedy( &player, &enemies, &mut init_hp_sums, &mut enemies_score_sums, ); let (_move_success, dir) = player.move_to_target(target_x, &mut enemies); println!("{}", dir); // flush std::io::stdout().flush().unwrap(); postprocess(&mut enemies, &mut player, &mut init_hp_sums); turn += 1; if turn > 1000 { break; } } eprintln!("{}", player.score); } fn abs_diff(a: usize, b: usize) -> usize { if a > b { a - b } else { b - a } } fn greedy( player: &Player, enemies: &Vec>, init_hp_sums: &mut Vec, enemies_score_sum: &mut Vec, ) -> usize { for i in 0..WIDTH { enemies_score_sum[i] = 0.; for j in 0..WIDTH { enemies_score_sum[i] += init_hp_sums[j] as f64 / (1 + abs_diff(i, j)).pow(2) as f64; } } let mut cand_enemies = vec![]; for i in 0..WIDTH { if !enemies[i].is_empty() { cand_enemies.push(enemies[i][0].clone()); } } let mut best_target_x = None; let mut best_value = 0.; let t = 0.15; // 決め打ち for &enemy in cand_enemies.iter() { let value = enemy.evaluation(player); let use_turn = compute_attack_turn(player, enemies, enemy.x); if use_turn == INF { continue; } let value = value as f64 / use_turn as f64 + enemies_score_sum[enemy.x] * t * f64::min(1., player.level as f64 / TARGET_LEVEL as f64); if best_target_x.is_none() || value > best_value { best_target_x = Some(enemy.x); best_value = value; } } if best_target_x.is_none() { // だめかもしれないがとりあえず return player.x; } else { return best_target_x.unwrap(); } } fn compute_attack_turn(player: &Player, enemies: &Vec>, target_x: usize) -> usize { let mut turn = compute_approach_turn(player, enemies, target_x); if turn == INF { return INF; } // 移動して攻撃も、移動せず攻撃も使うターンは同じ if turn > 0 { turn -= 1; } let breaking_turn = (enemies[target_x][0].now_hp + player.level - 1) / player.level; turn += breaking_turn; // 破壊までの合計ターンよりy=0に来るのがINFを返す if turn > enemies[target_x][0].y { return INF; } turn } // 目標地点までの最短ターン数を計算する。 fn compute_approach_turn( player: &Player, enemies: &Vec>, target_x: usize, ) -> usize { let mut turn = 0; let mut player = player.clone(); let mut enemies = enemies.clone(); // preprocessとpostprocessを使う用のダミー let mut init_hp_sums = vec![INF; WIDTH]; while player.x != target_x { if turn != 0 { preprocess(&mut enemies, vec![], &mut init_hp_sums) } let (move_success, _) = player.move_to_target(target_x, &mut enemies); if !move_success { return INF; } postprocess(&mut enemies, &mut player, &mut init_hp_sums); turn += 1; } turn } fn diff_and_dir(x1: usize, x2: usize) -> (usize, char) { if x1 == x2 { return (0, 'S'); } let d1 = (x1 + WIDTH - x2) % WIDTH; let d2 = (x2 + WIDTH - x1) % WIDTH; if d1 < d2 { (d1, 'L') } else { (d2, 'R') } } fn preprocess( enemies: &mut Vec>, new_enemies: Vec, init_hp_sums: &mut Vec, ) { for i in 0..WIDTH { if !enemies[i].is_empty() && enemies[i][0].y == 0 { init_hp_sums[i] -= enemies[i][0].init_hp; enemies[i].pop_front(); } for enemy in enemies[i].iter_mut() { enemy.y -= 1; } } for enemy in new_enemies.into_iter() { enemies[enemy.x].push_back(enemy); init_hp_sums[enemy.x] += enemy.init_hp; } } fn postprocess( enemies: &mut Vec>, player: &mut Player, init_hp_sums: &mut Vec, ) { let x = player.x; if !enemies[x].is_empty() { if enemies[x][0].now_hp <= player.level { player.score += enemies[x][0].init_hp; player.total_power += enemies[x][0].power; player.level = 1 + player.total_power / 100; init_hp_sums[x] -= enemies[x][0].init_hp; enemies[x].pop_front(); } else { enemies[x][0].now_hp -= player.level; } } } fn read_input() -> Option> { let mut input_line = String::new(); io::stdin().read_line(&mut input_line).unwrap(); let n = parse_input!(input_line, i32); if n < 0 { return None; } let mut enemies = vec![]; for _ in 0..n { let mut input_line = String::new(); io::stdin().read_line(&mut input_line).unwrap(); let inputs = input_line.split(' ').collect::>(); let enemy = vec![ parse_input!(inputs[0], usize), parse_input!(inputs[1], usize), parse_input!(inputs[2], usize), ]; enemies.push(Enemy::new(enemy)); } Some(enemies) } #[derive(Clone, Copy, Debug)] struct Player { x: usize, level: usize, total_power: usize, score: usize, } impl Player { fn new() -> Self { Self { x: CENTER, level: 1, total_power: 0, score: 0, } } fn move_left(&mut self) { if self.x > 0 { self.x -= 1; } else { self.x = WIDTH - 1; } } fn move_right(&mut self) { if self.x < WIDTH - 1 { self.x += 1; } else { self.x = 0; } } fn move_to_target( &mut self, target_x: usize, enemies: &mut Vec>, ) -> (bool, char) { let (_, dir) = diff_and_dir(self.x, target_x); // いけそうなら行く。駄目ならその場で待機 let mut final_dir = dir; if dir == 'R' { self.move_right(); if !enemies[self.x].is_empty() && enemies[self.x][0].y == 1 { self.move_left(); final_dir = 'S'; } } else if dir == 'L' { self.move_left(); if !enemies[self.x].is_empty() && enemies[self.x][0].y == 1 { self.move_right(); final_dir = 'S'; } } let success = enemies[self.x].is_empty() || enemies[self.x][0].y != 1; (success, final_dir) } } #[derive(Clone, Copy, Debug)] struct Enemy { init_hp: usize, now_hp: usize, power: usize, x: usize, y: usize, } impl Enemy { fn new(hpx: Vec) -> Self { let init_hp = hpx[0]; let power = hpx[1]; let x = hpx[2]; Self { init_hp, now_hp: init_hp, power, x, y: HEIGHT - 1, } } fn evaluation(&self, player: &Player) -> f64 { let t = f64::min(1.0, player.level as f64 / TARGET_LEVEL as f64); self.power as f64 * (1.0 - t) + self.init_hp as f64 * t } }