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

• 問題: No.5017 Tool-assisted Shooting
• ユーザー: gobi_503
• 提出日時: 2023-07-16 18:59:00
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 77 ms / 2,000 ms
• コード長: 16,287 bytes
• コンパイル時間: 2,057 ms
• コンパイル使用メモリ: 167,256 KB
• 実行使用メモリ: 24,432 KB
• スコア: 3,102,578
• 平均クエリ数: 893.15
• 最終ジャッジ日時: 2023-07-16 19:01:05
• 合計ジャッジ時間: 13,908 ms
• ジャッジサーバーID （参考情報）: judge17 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	34 ms; 23,844 KB
testcase_01	AC	69 ms; 24,036 KB
testcase_02	AC	67 ms; 23,844 KB
testcase_03	AC	36 ms; 23,664 KB
testcase_04	AC	68 ms; 23,544 KB
testcase_05	AC	68 ms; 23,640 KB
testcase_06	AC	69 ms; 24,432 KB
testcase_07	AC	39 ms; 23,724 KB
testcase_08	AC	67 ms; 23,400 KB
testcase_09	AC	68 ms; 24,348 KB
testcase_10	AC	35 ms; 23,388 KB
testcase_11	AC	76 ms; 24,288 KB
testcase_12	AC	68 ms; 23,424 KB
testcase_13	AC	69 ms; 23,628 KB
testcase_14	AC	69 ms; 23,676 KB
testcase_15	AC	75 ms; 24,036 KB
testcase_16	AC	74 ms; 23,532 KB
testcase_17	AC	75 ms; 24,000 KB
testcase_18	AC	75 ms; 23,532 KB
testcase_19	AC	39 ms; 24,000 KB
testcase_20	AC	76 ms; 23,544 KB
testcase_21	AC	77 ms; 24,012 KB
testcase_22	AC	69 ms; 24,360 KB
testcase_23	AC	56 ms; 24,276 KB
testcase_24	AC	68 ms; 23,844 KB
testcase_25	AC	68 ms; 24,300 KB
testcase_26	AC	33 ms; 23,640 KB
testcase_27	AC	69 ms; 24,336 KB
testcase_28	AC	69 ms; 24,048 KB
testcase_29	AC	69 ms; 23,676 KB
testcase_30	AC	68 ms; 23,832 KB
testcase_31	AC	68 ms; 23,412 KB
testcase_32	AC	68 ms; 23,676 KB
testcase_33	AC	69 ms; 23,388 KB
testcase_34	AC	75 ms; 23,676 KB
testcase_35	AC	69 ms; 23,676 KB
testcase_36	AC	69 ms; 23,628 KB
testcase_37	AC	69 ms; 23,520 KB
testcase_38	AC	69 ms; 23,532 KB
testcase_39	AC	31 ms; 23,652 KB
testcase_40	AC	32 ms; 24,384 KB
testcase_41	AC	68 ms; 23,424 KB
testcase_42	AC	69 ms; 24,060 KB
testcase_43	AC	68 ms; 23,544 KB
testcase_44	AC	70 ms; 23,556 KB
testcase_45	AC	69 ms; 23,628 KB
testcase_46	AC	69 ms; 24,324 KB
testcase_47	AC	69 ms; 23,532 KB
testcase_48	AC	69 ms; 24,372 KB
testcase_49	AC	68 ms; 23,388 KB
testcase_50	AC	68 ms; 24,372 KB
testcase_51	AC	69 ms; 24,048 KB
testcase_52	AC	69 ms; 24,060 KB
testcase_53	AC	75 ms; 23,520 KB
testcase_54	AC	68 ms; 23,424 KB
testcase_55	AC	68 ms; 24,360 KB
testcase_56	AC	69 ms; 24,240 KB
testcase_57	AC	68 ms; 23,856 KB
testcase_58	AC	69 ms; 23,844 KB
testcase_59	AC	70 ms; 23,400 KB
testcase_60	AC	68 ms; 24,036 KB
testcase_61	AC	69 ms; 23,652 KB
testcase_62	AC	68 ms; 24,300 KB
testcase_63	AC	70 ms; 24,000 KB
testcase_64	AC	69 ms; 23,664 KB
testcase_65	AC	70 ms; 23,832 KB
testcase_66	AC	69 ms; 24,348 KB
testcase_67	AC	69 ms; 23,988 KB
testcase_68	AC	68 ms; 23,604 KB
testcase_69	AC	68 ms; 23,400 KB
testcase_70	AC	75 ms; 23,388 KB
testcase_71	AC	69 ms; 23,388 KB
testcase_72	AC	69 ms; 23,388 KB
testcase_73	AC	71 ms; 23,676 KB
testcase_74	AC	45 ms; 24,384 KB
testcase_75	AC	70 ms; 24,360 KB
testcase_76	AC	68 ms; 24,288 KB
testcase_77	AC	69 ms; 23,628 KB
testcase_78	AC	71 ms; 23,652 KB
testcase_79	AC	70 ms; 24,036 KB
testcase_80	AC	32 ms; 24,384 KB
testcase_81	AC	70 ms; 24,360 KB
testcase_82	AC	69 ms; 23,640 KB
testcase_83	AC	69 ms; 23,436 KB
testcase_84	AC	68 ms; 24,408 KB
testcase_85	AC	69 ms; 24,276 KB
testcase_86	AC	33 ms; 24,048 KB
testcase_87	AC	69 ms; 23,424 KB
testcase_88	AC	69 ms; 24,264 KB
testcase_89	AC	74 ms; 24,012 KB
testcase_90	AC	68 ms; 24,372 KB
testcase_91	AC	69 ms; 23,676 KB
testcase_92	AC	32 ms; 24,012 KB
testcase_93	AC	69 ms; 23,592 KB
testcase_94	AC	69 ms; 24,000 KB
testcase_95	AC	69 ms; 24,000 KB
testcase_96	AC	68 ms; 24,384 KB
testcase_97	AC	68 ms; 24,036 KB
testcase_98	AC	72 ms; 23,664 KB
testcase_99	AC	41 ms; 23,616 KB

コンパイルメッセージ

warning: function `usize_abs` is never used
  --> Main.rs:74:4
   |
74 | fn usize_abs(a: usize, b: usize) -> usize {
   |    ^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: associated function `list` is never used
   --> Main.rs:188:8
    |
188 |     fn list() -> Vec<Self> {
    |        ^^^^

warning: 2 warnings emitted

ソースコード

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_imports)]
use std::io::Write;
use std::time::SystemTime;

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        #[allow(unused_imports)]
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

#[macro_export]
macro_rules! mat {
	($($e:expr),*) => { Vec::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

pub trait SetMinMax {
    fn setmin(&mut self, v: Self) -> bool;
    fn setmax(&mut self, v: Self) -> bool;
}
impl<T> SetMinMax for T
where
    T: PartialOrd,
{
    fn setmin(&mut self, v: T) -> bool {
        *self > v && {
            *self = v;
            true
        }
    }
    fn setmax(&mut self, v: T) -> bool {
        *self < v && {
            *self = v;
            true
        }
    }
}

fn usize_abs(a: usize, b: usize) -> usize {
    if a > b {
        a - b
    } else {
        b - a
    }
}

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Coord {
    pub x: isize,
    pub y: isize,
}
#[allow(dead_code)]
impl Coord {
    pub fn new(p: (isize, isize)) -> Self {
        Coord { x: p.0, y: p.1 }
    }
    pub fn from_usize_pair(p: (usize, usize)) -> Self {
        Coord {
            x: p.0 as isize,
            y: p.1 as isize,
        }
    }

    pub fn in_field(&self) -> bool {
        (0 <= self.x && self.x < WIDTH as isize) && (0 <= self.y && self.y < HEIGHT as isize)
    }

    // ペアへの変換
    pub fn to_pair(&self) -> (isize, isize) {
        (self.x, self.y)
    }
    pub fn to_usize_pair(&self) -> (usize, usize) {
        (self.x as usize, self.y as usize)
    }

    // マンハッタン距離
    pub fn distance(&self, that: &Self) -> isize {
        (self.x - that.x).abs() + (self.y - that.y).abs()
    }

    pub fn mk_4dir(&self) -> Vec<Self> {
        let delta = [(-1, 0), (1, 0), (0, -1), (0, 1)];

        delta
            .iter()
            .map(|&p| self.plus(&Coord::new(p)))
            .filter(|&pos| pos.in_field())
            .collect()
    }

    pub fn com_to_delta(com: char) -> Self {
        match com {
            'U' => Coord::new((0, -1)),
            'D' => Coord::new((0, 1)),
            'L' => Coord::new((-1, 0)),
            'R' => Coord::new((1, 0)),
            _ => unreachable!(),
        }
    }

    // 四則演算
    pub fn plus(&self, that: &Self) -> Self {
        Coord::new((self.x + that.x, self.y + that.y))
    }
    pub fn minus(&self, that: &Self) -> Self {
        Coord::new((self.x - that.x, self.y - that.y))
    }

    pub fn access_matrix<'a, T>(&'a self, mat: &'a Vec<Vec<T>>) -> &'a T {
        &mat[self.y as usize][self.x as usize]
    }

    pub fn set_matrix<T>(&self, mat: &mut Vec<Vec<T>>, e: T) {
        mat[self.y as usize][self.x as usize] = e;
    }
}
// println!("{}") での表示内容
impl std::fmt::Display for Coord {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "({}, {})", self.x, self.y)?;
        Ok(())
    }
}
// println!("{:?}") での表示内容
impl std::fmt::Debug for Coord {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "({}, {})", self.x, self.y)?;
        Ok(())
    }
}

const WIDTH: usize = 25;
const HEIGHT: usize = 60;
#[allow(dead_code)]
const ENEMY_NUM_MAX: usize = 25;
const MAX_TURN: usize = 1_000;

#[derive(Clone, Copy, Debug, PartialEq)]
enum Command {
    Left,
    Right,
    Stay,
}
impl Command {
    fn to_string(&self) -> &str {
        match self {
            Command::Left => "L",
            Command::Right => "R",
            Command::Stay => "S",
        }
    }

    fn list() -> Vec<Self> {
        vec![Command::Left, Command::Right, Command::Stay]
    }

    fn move_num(&self) -> usize {
        match self {
            Command::Left => WIDTH - 1,
            Command::Right => 1,
            Command::Stay => 0,
        }
    }
}

#[derive(Clone, Copy, Debug)]
struct Enemy {
    hp: usize,    // HP (自機レベルが１ターンの与ダメージ。倒すとHP分のスコアが得られる。)
    power: usize, // パワー (100ごとに自機のレベルが１上がる)
    x: usize,     // x座標

    score: usize, // 倒したときのスコア
}
impl Enemy {
    fn new(hp: usize, power: usize, x: usize) -> Self {
        Self {
            hp,
            power,
            x,
            score: hp,
        }
    }
}

#[allow(dead_code)]
struct Input {
    n: usize,
    enemies: Vec<Enemy>,
}
impl Input {
    fn new(n: usize, sc: &mut IO<std::io::StdinLock<'_>, std::io::StdoutLock<'_>>) -> Self {
        let mut enemies = vec![];
        for _ in 0..n {
            let v = (0..3).map(|_| sc.read::<usize>()).collect::<Vec<_>>();
            let e = Enemy::new(v[0], v[1], v[2]);
            enemies.push(e);
        }

        Self { n, enemies }
    }
}

#[derive(Clone, Debug)]
struct State {
    me: usize,  // 自機のx座標
    exp: usize, // 破壊敵機のパワーの通算。100ごとにレベルアップ。

    turn: usize, // 現在のターン数
    field: Vec<Vec<Option<Enemy>>>,
    score: usize,
}
impl State {
    fn new() -> Self {
        Self {
            me: 12,
            exp: 0,
            turn: 0,
            field: mat![None; HEIGHT; WIDTH],
            score: 0,
        }
    }

    fn get_level(&self) -> usize {
        1 + self.exp / 100
    }

    // inputを反映させる更新
    // 1. フィールドに存在する全ての敵機が下に1マス移動する。フィールド外に移動した敵機は消滅する。
    // 2. 一番上の行に新たな敵機が出現する。出現確率は後述のように列ごとに定められている。
    // => isLive
    fn update_by_input(&mut self, input: &Input) -> bool {
        let mut new_row = vec![None; WIDTH];
        for e in input.enemies.iter() {
            new_row[e.x] = Some(e.clone());
        }

        self.field.remove(0);
        self.field.push(new_row);

        if self.field[0][self.me].is_some() {
            eprintln!("Game Over. ターン: {}, スコア: {}", self.turn, self.score);
            return false;
        }

        true
    }

    // シミュレーション用
    fn update_by_empty_input(&mut self) -> bool {
        let new_row = vec![None; WIDTH];

        self.field.remove(0);
        self.field.push(new_row);

        if self.field[0][self.me].is_some() {
            return false;
        }
        true
    }

    // 3. 自機を左右いずれかに1マス移動、またはその場にとどまる。
    // 4. 自機と同じ列に存在する敵機の中で自機に一番近い敵機を自動で攻撃する。
    // => isLive
    fn update_by_cmd(&mut self, cmd: &Command) -> bool {
        // 移動
        self.me = (self.me + cmd.move_num()) % WIDTH;

        // 射撃
        let x = self.me;
        if let Some(ene_pos) = self.find_nearest_on_col(x) {
            let (_, y) = ene_pos.to_usize_pair();

            let mut enemy = self.field[y][x].clone().unwrap();
            if enemy.hp <= self.get_level() {
                self.score += enemy.score;
                self.exp += enemy.power;
                self.field[y][x] = None;
            } else {
                enemy.hp -= self.get_level();
                self.field[y][x] = Some(enemy)
            }
        }

        if self.field[0][self.me].is_some() {
            return false;
        }
        true
    }

    // 指定したカラムの一番下に居る敵機の座標を返す
    fn find_nearest_on_col(&self, x: usize) -> Option<Coord> {
        let mut res = None;

        for y in 1..HEIGHT {
            if self.field[y][x].is_some() {
                res = Some(Coord::from_usize_pair((x, y)));
                break;
            }
        }

        res
    }

    /* user define */
    // 最速で倒せるx座標を返す
    fn search_fastest_break(&self, excludes: &Vec<usize>) -> Option<usize> {
        let mut row = vec![4242; WIDTH];
        let level = self.get_level();

        let init_x = self.me;
        if let Some(enemy_pos) = self.find_nearest_on_col(init_x) {
            let enemy = enemy_pos.access_matrix(&self.field).unwrap();
            // 所要ターン数
            let turn = (enemy.hp + level - 1) / level;

            if turn <= enemy_pos.y as usize {
                row[init_x] = turn;
            }
        }

        for i in 1..=WIDTH / 2 {
            // [右移動, 左移動]
            for x in [(init_x + i) % WIDTH, (init_x + WIDTH - i) % WIDTH] {
                if excludes.contains(&x) {
                    continue;
                }

                if let Some(enemy_pos) = self.find_nearest_on_col(x) {
                    let enemy = enemy_pos.access_matrix(&self.field).unwrap();
                    // 所要ターン数 ((i-1)は移動分)
                    let turn = (enemy.hp + level - 1) / level + (i - 1);

                    if turn <= enemy_pos.y as usize {
                        row[x] = turn;
                    }
                }
            }
        }

        let mut res = None;
        let mut best = 4242;
        for x in 0..WIDTH {
            if row[x] < best {
                res = Some(x);
                best = row[x];
            }
        }

        res
    }

    fn search_better_score(&self, excludes: &Vec<usize>) -> Option<usize> {
        let mut row = vec![0.0; WIDTH];
        let level = self.get_level();

        let init_x = self.me;
        if let Some(enemy_pos) = self.find_nearest_on_col(init_x) {
            let enemy = enemy_pos.access_matrix(&self.field).unwrap();
            // 所要ターン数
            let turn = (enemy.hp + level - 1) / level;

            if turn <= enemy_pos.y as usize {
                let rate = enemy.power as f64 / turn as f64;
                row[init_x] = rate;
            }
        }

        for i in 1..=WIDTH / 2 {
            // [右移動, 左移動]
            for x in [(init_x + i) % WIDTH, (init_x + WIDTH - i) % WIDTH] {
                if excludes.contains(&x) {
                    continue;
                }

                if let Some(enemy_pos) = self.find_nearest_on_col(x) {
                    let enemy = enemy_pos.access_matrix(&self.field).unwrap();
                    // 所要ターン数 ((i-1)は移動分)
                    let turn = (enemy.hp + level - 1) / level + (i - 1);

                    if turn <= enemy_pos.y as usize {
                        let rate = enemy.power as f64 / turn as f64;
                        row[x] = rate;
                    }
                }
            }
        }

        let mut res = None;
        let mut best = 0.0;
        for x in 0..WIDTH {
            if row[x] > best {
                res = Some(x);
                best = row[x];
            }
        }

        res
    }
}

fn main() {
    let system_time = SystemTime::now();

    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let mut st = State::new();
    for turn in 1..=MAX_TURN {
        st.turn = turn;
        // eprintln!("turn: {}", turn);

        /* input & update */
        let n: isize = sc.read();
        if n == -1 {
            break;
        }
        let n = n as usize;
        let input = Input::new(n, &mut sc);

        st.update_by_input(&input);

        /* solve */
        let mut cmd = Command::Stay;

        let mut flag = false;
        if turn >= 2000 {
            let mut excledes = vec![];
            loop {
                if let Some(x) = st.search_better_score(&excledes) {
                    // 自機ポジションを原点とするx座標
                    let offset = (x + WIDTH - st.me) % WIDTH;
                    if offset == 0 {
                        cmd = Command::Stay;
                    } else if offset <= WIDTH / 2 {
                        cmd = Command::Right;
                    } else {
                        cmd = Command::Left;
                    }

                    // ダメだったらexcludesに追加
                    if !can_move(st.clone(), x, &cmd) {
                        excledes.push(x);
                    } else {
                        flag = true;
                        // eprintln!("turn: {}", turn);
                        break;
                    }
                } else {
                    break;
                }
            }
        }

        if !flag {
            let mut excledes = vec![];
            loop {
                if let Some(x) = st.search_fastest_break(&excledes) {
                    // 自機ポジションを原点とするx座標
                    let offset = (x + WIDTH - st.me) % WIDTH;
                    if offset == 0 {
                        cmd = Command::Stay;
                    } else if offset <= WIDTH / 2 {
                        cmd = Command::Right;
                    } else {
                        cmd = Command::Left;
                    }

                    // ダメだったらexcludesに追加
                    if !can_move(st.clone(), x, &cmd) {
                        excledes.push(x);
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
            // stayして死ぬなら右に移動
            if let Some(enemy) = st.field[1][st.me as usize] {
                if cmd == Command::Stay {
                    if enemy.hp > st.get_level() {
                        cmd = Command::Right;
                    }
                }
            }

            if turn == 231 {
                eprintln!("{:?}", st.field[1]);
            }
            // TODO: アドホックなfixなので
            match cmd {
                Command::Right => {
                    let x = (st.me + 1) % WIDTH;
                    if let Some(ene) = st.field[1][x] {
                        if ene.hp > st.get_level() {
                            cmd = Command::Stay;
                        }
                    }
                }
                Command::Left => {
                    let x = (st.me + WIDTH - 1) % WIDTH;
                    if let Some(ene) = st.field[1][x] {
                        if ene.hp > st.get_level() {
                            cmd = Command::Stay;
                        }
                    }
                }
                Command::Stay => {}
            }
        }

        /* output & update */
        println!("{}", cmd.to_string());
        // println!("#{}", cmd.to_string());
        st.update_by_cmd(&cmd);

        // eprintln!("score {}: {}", turn, st.score);
    }

    eprintln!("{}ms", system_time.elapsed().unwrap().as_millis());
    eprintln!("score: {}", st.score);
}

fn can_move(mut st: State, x: usize, dir: &Command) -> bool {
    if *dir == Command::Stay {
        return true;
    }

    while st.me != x {
        if !st.update_by_cmd(dir) {
            return false;
        }
        if !st.update_by_empty_input() {
            return false;
        }
    }
    true
}