結果

問題 No.5017 Tool-assisted Shooting
ユーザー pokapoka
提出日時 2023-07-29 14:09:56
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 RE -
testcase_61 RE -
testcase_62 RE -
testcase_63 RE -
testcase_64 RE -
testcase_65 RE -
testcase_66 RE -
testcase_67 RE -
testcase_68 RE -
testcase_69 RE -
testcase_70 RE -
testcase_71 RE -
testcase_72 RE -
testcase_73 RE -
testcase_74 RE -
testcase_75 RE -
testcase_76 RE -
testcase_77 RE -
testcase_78 RE -
testcase_79 RE -
testcase_80 RE -
testcase_81 RE -
testcase_82 RE -
testcase_83 AC 94 ms
23,664 KB
testcase_84 RE -
testcase_85 RE -
testcase_86 RE -
testcase_87 RE -
testcase_88 RE -
testcase_89 RE -
testcase_90 RE -
testcase_91 RE -
testcase_92 RE -
testcase_93 RE -
testcase_94 RE -
testcase_95 RE -
testcase_96 RE -
testcase_97 RE -
testcase_98 RE -
testcase_99 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
            }
        }
    }
}
0