結果
問題 | No.5017 Tool-assisted Shooting |
ユーザー |
![]() |
提出日時 | 2023-07-16 17:31:14 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 180 ms / 2,000 ms |
コード長 | 9,500 bytes |
コンパイル時間 | 1,879 ms |
コンパイル使用メモリ | 152,420 KB |
実行使用メモリ | 24,336 KB |
スコア | 4,252,507 |
平均クエリ数 | 1000.00 |
最終ジャッジ日時 | 2023-07-16 17:31:39 |
合計ジャッジ時間 | 23,106 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
use std::io::Write;macro_rules! get {($t:ty) => {{let mut line: String = String::new();std::io::stdin().read_line(&mut line).unwrap();line.trim().parse::<$t>().unwrap()}};($($t:ty),*) => {{let mut line: String = String::new();std::io::stdin().read_line(&mut line).unwrap();let mut iter = line.split_whitespace();($(iter.next().unwrap().parse::<$t>().unwrap(),)*)}};($t:ty; $n:expr) => {(0..$n).map(|_|get!($t)).collect::<Vec<_>>()};($($t:ty),*; $n:expr) => {(0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()};($t:ty ;;) => {{let mut line: String = String::new();std::io::stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t| t.parse::<$t>().unwrap()).collect::<Vec<_>>()}};($t:ty ;; $n:expr) => {(0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()};}pub trait ChangeMinMax {fn change_min(&mut self, v: Self) -> bool;fn change_max(&mut self, v: Self) -> bool;}impl<T: PartialOrd> ChangeMinMax for T {fn change_min(&mut self, v: T) -> bool {*self > v && {*self = v;true}}fn change_max(&mut self, v: T) -> bool {*self < v && {*self = v;true}}}const MAX_TURN: usize = 1000;const DEFAULT_SIMULATION_LEN: usize = 15;const HEIGHT: usize = 60;const WIDTH: usize = 25;const CENTER: usize = 12;const L: usize = !0;const C: usize = 0;const R: usize = 1;#[derive(Debug, Clone)]struct State {column: usize,power: u32,raw_score: u32,score: f64,turn: usize,enemies: EnemyState,}impl State {fn new() -> Self {Self {column: CENTER,power: 100,raw_score: 0,turn: 0,score: 0.0,enemies: EnemyState::new(),}}fn level(&self) -> u32 {self.power / 100}fn move_player(&mut self, direction: usize) {self.column = (self.column + direction + WIDTH) % WIDTH;}fn attack(&mut self, enemy_collection: &EnemyCollection) {let level = self.level();if self.enemies.has_enemy(enemy_collection, self.column) {let (hp, power) = self.enemies.damage(enemy_collection, self.column, level);self.raw_score += hp;self.power += power;}}fn progress_turn(&mut self, enemy_collection: &EnemyCollection, direction: usize) -> bool {let mut alive = true;self.enemies.clean_up_enemies(enemy_collection, self.turn);alive &= !self.enemies.crash(enemy_collection, self.column, self.turn);self.move_player(direction);alive &= !self.enemies.crash(enemy_collection, self.column, self.turn);self.attack(enemy_collection);self.turn += 1;self.update_score(enemy_collection);alive}fn update_score(&mut self, enemy_collection: &EnemyCollection) {let mut raw_score_point = self.raw_score as f64;let mut power_point = self.power as f64;let cols = [((self.column + WIDTH - L) % WIDTH, 0.5),(self.column, 1.0),((self.column + R) % WIDTH, 0.5),];for &(col, coef) in &cols {if let Some(enemy) = self.enemies.get(enemy_collection, col) {let ratio = self.enemies.damages[col] as f64 / enemy.hp as f64;let coef = coef * ratio * ratio * 0.5;raw_score_point += enemy.hp as f64 * coef;power_point += enemy.power as f64 * coef;}}let raw_score_coef = self.turn as f64;let power_point_coef = (MAX_TURN - self.turn) as f64;self.score = raw_score_point * raw_score_coef + power_point * power_point_coef;}}#[derive(Debug, Clone, Copy, Default)]struct Enemy {hp: u32,power: u32,spawn_turn: usize,}impl Enemy {fn new(hp: u32, power: u32, spawn_turn: usize) -> Self {Self {hp,power,spawn_turn,}}fn is_out_of_range(&self, turn: usize) -> bool {self.spawn_turn + HEIGHT <= turn}fn is_bottom(&self, turn: usize) -> bool {self.spawn_turn + HEIGHT - 1 == turn}}#[derive(Debug, Clone)]struct EnemyState {indices: [usize; WIDTH],damages: [u32; WIDTH],}impl EnemyState {fn new() -> Self {Self {indices: [0; WIDTH],damages: [0; WIDTH],}}fn has_enemy(&self, enemies: &EnemyCollection, column: usize) -> bool {self.get(enemies, column).is_some()}fn get<'a>(&self, enemies: &'a EnemyCollection, column: usize) -> Option<&'a Enemy> {enemies.get(column, self.indices[column])}fn crash(&self, enemies: &EnemyCollection, column: usize, turn: usize) -> bool {if let Some(enemy) = enemies.get(column, self.indices[column]) {enemy.is_bottom(turn)} else {false}}fn damage(&mut self, enemies: &EnemyCollection, column: usize, attack: u32) -> (u32, u32) {let enemy = enemies.get(column, self.indices[column]).unwrap();self.damages[column] += attack;if self.damages[column] >= enemy.hp {self.damages[column] = 0;self.indices[column] += 1;(enemy.hp, enemy.power)} else {(0, 0)}}fn clean_up_enemies(&mut self, enemies: &EnemyCollection, turn: usize) {for (column, (index, damage)) in self.indices.iter_mut().zip(self.damages.iter_mut()).enumerate(){if let Some(enemy) = enemies.get(column, *index) {if enemy.is_out_of_range(turn) {*damage = 0;*index += 1;}}}}}#[derive(Debug, Clone)]struct EnemyCollection {enemies: Vec<Vec<Enemy>>,}impl EnemyCollection {fn new() -> Self {Self {enemies: vec![vec![]; WIDTH],}}fn spawn(&mut self, enemies: &[(u32, u32, usize)], turn: usize) {for &(hp, power, col) in enemies {self.enemies[col].push(Enemy::new(hp, power, turn));}}fn get(&self, column: usize, index: usize) -> Option<&Enemy> {self.enemies[column].get(index)}}fn main() {let mut state = State::new();let mut enemy_collection = EnemyCollection::new();let mut turn = 0;while let Some(enemies) = read_spawns() {enemy_collection.spawn(&enemies, turn);let mut current_states = vec![None; WIDTH];current_states[state.column] = Some((state.clone(), C));let simulation_len = DEFAULT_SIMULATION_LEN.min(MAX_TURN - turn);for iter in 0..simulation_len {let mut next_states: Vec<Option<(State, usize)>> = vec![None; WIDTH];for state in current_states.iter() {if let Some((state, first_dir)) = state {for &dir in &[L, C, R] {let mut state = state.clone();let is_alive = state.progress_turn(&enemy_collection, dir);if !is_alive {continue;}let next_col = state.column;if next_states[next_col].as_ref().map_or(std::f64::MIN, |s| s.0.score)< state.score{let dir = if iter == 0 { dir } else { *first_dir };next_states[next_col] = Some((state, dir));}}}}current_states = next_states;}let mut best_score = std::f64::MIN;let mut best_dir = C;for s in current_states.iter() {if let Some((state, dir)) = s {if best_score.change_max(state.score) {best_dir = *dir;}}}write_direction(best_dir);state.progress_turn(&enemy_collection, best_dir);turn += 1;eprintln!("power: {}", state.power);eprintln!("score: {}", state.raw_score);eprintln!("turn: {}", turn + 1);eprintln!("best_score: {}", best_score);eprintln!("");if turn == MAX_TURN {break;}}}fn read_spawns() -> Option<Vec<(u32, u32, usize)>> {let n = get!(i32);if n < 0 {return None;}let mut enemies = vec![];for _ in 0..n {enemies.push(get!(u32, u32, usize));}Some(enemies)}fn write_direction(direction: usize) {match direction {L => println!("L"),C => println!("S"),R => println!("R"),_ => unreachable!(),}std::io::stdout().flush().unwrap();}