結果

問題 No.5017 Tool-assisted Shooting
ユーザー pokapoka
提出日時 2023-07-29 15:04:07
言語 Rust
(1.77.0)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 8,315 bytes
コンパイル時間 6,260 ms
コンパイル使用メモリ 154,252 KB
実行使用メモリ 24,444 KB
スコア 4,297,532
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-29 15:04:30
合計ジャッジ時間 21,296 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 107 ms
24,336 KB
testcase_01 AC 106 ms
23,616 KB
testcase_02 AC 92 ms
24,036 KB
testcase_03 AC 102 ms
23,604 KB
testcase_04 AC 98 ms
23,544 KB
testcase_05 AC 98 ms
24,408 KB
testcase_06 AC 102 ms
24,060 KB
testcase_07 AC 102 ms
24,012 KB
testcase_08 AC 99 ms
23,616 KB
testcase_09 AC 99 ms
24,432 KB
testcase_10 AC 102 ms
23,544 KB
testcase_11 AC 98 ms
24,192 KB
testcase_12 AC 98 ms
23,340 KB
testcase_13 AC 103 ms
23,496 KB
testcase_14 AC 104 ms
23,952 KB
testcase_15 AC 100 ms
23,400 KB
testcase_16 AC 98 ms
24,348 KB
testcase_17 AC 104 ms
23,808 KB
testcase_18 AC 100 ms
23,952 KB
testcase_19 AC 105 ms
23,388 KB
testcase_20 AC 101 ms
24,192 KB
testcase_21 AC 104 ms
24,264 KB
testcase_22 AC 95 ms
23,532 KB
testcase_23 AC 98 ms
24,036 KB
testcase_24 AC 104 ms
23,352 KB
testcase_25 AC 107 ms
24,012 KB
testcase_26 AC 100 ms
24,444 KB
testcase_27 AC 99 ms
24,336 KB
testcase_28 AC 106 ms
24,012 KB
testcase_29 AC 96 ms
23,676 KB
testcase_30 AC 95 ms
23,340 KB
testcase_31 AC 99 ms
23,532 KB
testcase_32 AC 103 ms
24,396 KB
testcase_33 AC 106 ms
23,832 KB
testcase_34 AC 102 ms
23,376 KB
testcase_35 AC 101 ms
24,000 KB
testcase_36 AC 99 ms
24,024 KB
testcase_37 AC 102 ms
23,952 KB
testcase_38 AC 102 ms
23,424 KB
testcase_39 AC 103 ms
23,964 KB
testcase_40 AC 104 ms
23,412 KB
testcase_41 AC 100 ms
23,808 KB
testcase_42 AC 103 ms
23,664 KB
testcase_43 AC 102 ms
23,988 KB
testcase_44 AC 103 ms
23,352 KB
testcase_45 AC 113 ms
23,640 KB
testcase_46 AC 107 ms
23,604 KB
testcase_47 AC 96 ms
23,988 KB
testcase_48 AC 103 ms
23,604 KB
testcase_49 AC 100 ms
23,640 KB
testcase_50 AC 102 ms
23,424 KB
testcase_51 AC 102 ms
23,388 KB
testcase_52 AC 104 ms
23,808 KB
testcase_53 AC 105 ms
24,228 KB
testcase_54 AC 103 ms
23,616 KB
testcase_55 AC 99 ms
23,580 KB
testcase_56 AC 103 ms
23,652 KB
testcase_57 AC 99 ms
23,340 KB
testcase_58 AC 102 ms
23,832 KB
testcase_59 AC 105 ms
24,000 KB
testcase_60 AC 101 ms
23,388 KB
testcase_61 AC 99 ms
24,060 KB
testcase_62 AC 124 ms
23,412 KB
testcase_63 AC 101 ms
23,664 KB
testcase_64 AC 103 ms
23,424 KB
testcase_65 AC 113 ms
23,628 KB
testcase_66 AC 105 ms
23,340 KB
testcase_67 AC 99 ms
23,412 KB
testcase_68 AC 101 ms
24,432 KB
testcase_69 AC 102 ms
23,604 KB
testcase_70 AC 126 ms
23,820 KB
testcase_71 AC 101 ms
23,796 KB
testcase_72 AC 92 ms
23,364 KB
testcase_73 AC 101 ms
24,180 KB
testcase_74 AC 93 ms
23,640 KB
testcase_75 AC 104 ms
23,496 KB
testcase_76 AC 101 ms
23,388 KB
testcase_77 AC 105 ms
24,372 KB
testcase_78 AC 101 ms
23,520 KB
testcase_79 AC 107 ms
24,024 KB
testcase_80 AC 103 ms
23,520 KB
testcase_81 AC 99 ms
23,496 KB
testcase_82 AC 100 ms
23,424 KB
testcase_83 AC 99 ms
23,436 KB
testcase_84 AC 101 ms
23,604 KB
testcase_85 AC 105 ms
24,012 KB
testcase_86 AC 102 ms
23,388 KB
testcase_87 AC 123 ms
23,664 KB
testcase_88 AC 106 ms
23,988 KB
testcase_89 AC 103 ms
23,400 KB
testcase_90 AC 104 ms
23,844 KB
testcase_91 AC 108 ms
23,796 KB
testcase_92 AC 93 ms
23,628 KB
testcase_93 AC 103 ms
24,264 KB
testcase_94 AC 95 ms
24,324 KB
testcase_95 AC 103 ms
23,664 KB
testcase_96 AC 104 ms
23,676 KB
testcase_97 AC 103 ms
24,312 KB
testcase_98 AC 101 ms
24,024 KB
testcase_99 AC 100 ms
23,676 KB
権限があれば一括ダウンロードができます

ソースコード

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);

        if !move_success {
            break;
        }

        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;
        }
        // eprintln!("value: {}", value);
        // eprintln!("use_turn: {}", use_turn);
        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;
        }
    }

    // eprintln!("best_target_x: {:?}", best_target_x);

    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