#896560 (Rust) No.5017 Tool-assisted Shooting

• 問題: No.5017 Tool-assisted Shooting
• ユーザー: poka
• 提出日時: 2023-07-29 14:09:56
• 言語: Rust (1.83.0 + proconio)
• 結果: RE
• 実行時間: -
• コード長: 8,898 bytes
• コンパイル時間: 4,123 ms
• コンパイル使用メモリ: 150,040 KB
• 実行使用メモリ: 24,540 KB
• スコア: 598,175
• 平均クエリ数: 396.15
• 最終ジャッジ日時: 2023-07-29 14:10:12
• 合計ジャッジ時間: 14,704 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

ファイルパターン	結果
other	AC * 1 RE * 99

ソースコード

use std::{collections::VecDeque, io::Write};

use yukicoder::io::Scanner;

const WIDTH: usize = 25;
const HEIGHT: usize = 60;
const CENTER: usize = WIDTH / 2;
const MAX_TURN: usize = 1000;
const TARGET_LEVEL: usize = 250; // 決め打ち
const INF: usize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    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];
    for _turn in 1..=MAX_TURN {
        let new_enemies = read_input(&mut sc);
        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);
    }
    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<VecDeque<Enemy>>,
    init_hp_sums: &mut Vec<usize>,
    enemies_score_sum: &mut Vec<f64>,
) -> 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<VecDeque<Enemy>>, 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<VecDeque<Enemy>>,
    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<VecDeque<Enemy>>,
    new_enemies: Vec<Enemy>,
    init_hp_sums: &mut Vec<usize>,
) {
    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<VecDeque<Enemy>>,
    player: &mut Player,
    init_hp_sums: &mut Vec<usize>,
) {
    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(sc: &mut Scanner) -> Vec<Enemy> {
    let n = sc.read::<usize>();
    let mut enemies = vec![];
    for _ in 0..n {
        let enemy = sc.read_vec::<usize>(3);
        enemies.push(Enemy::new(enemy));
    }
    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<VecDeque<Enemy>>,
    ) -> (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<usize>) -> 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
    }
}

mod yukicoder {
    pub mod io {
        use std::io::stdin;
        use std::str::FromStr;

        #[allow(dead_code)]
        pub struct Scanner {
            stdin: std::io::Stdin,
            buffer: Vec<String>,
        }

        #[allow(dead_code)]
        impl Scanner {
            pub fn new() -> Self {
                Self {
                    stdin: stdin(),
                    buffer: Vec::new(),
                }
            }

            pub fn read<T: FromStr>(&mut self) -> T {
                loop {
                    if let Some(token) = self.buffer.pop() {
                        return token.parse().ok().expect("Parse error");
                    }
                    let mut input = String::new();
                    self.stdin.read_line(&mut input).expect("IO error");
                    self.buffer = input.split_whitespace().rev().map(String::from).collect();
                }
            }

            pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
                (0..n).map(|_| self.read()).collect()
            }

            pub fn read_mat<T: FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
                (0..n).map(|_| self.read_vec(m)).collect()
            }

            pub fn read_chars(&mut self) -> Vec<char> {
                self.read::<String>().chars().collect()
            }
        }
    }
}