結果

問題 No.5017 Tool-assisted Shooting
ユーザー poka
提出日時 2023-07-29 14:38:51
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 102 ms / 2,000 ms
コード長 8,111 bytes
コンパイル時間 1,678 ms
コンパイル使用メモリ 168,112 KB
実行使用メモリ 24,408 KB
スコア 598,175
平均クエリ数 396.15
最終ジャッジ日時 2023-07-29 14:39:06
合計ジャッジ時間 12,401 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

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<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() -> Option<Vec<Enemy>> {
    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::<Vec<_>>();
        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<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
    }
}
0