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

• 問題: No.5017 Tool-assisted Shooting
• ユーザー: shamio
• 提出日時: 2023-07-16 19:19:48
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 104 ms / 2,000 ms
• コード長: 10,707 bytes
• コンパイル時間: 8,058 ms
• コンパイル使用メモリ: 206,484 KB
• 実行使用メモリ: 24,324 KB
• スコア: 3,455,069
• 平均クエリ数: 982.00
• 最終ジャッジ日時: 2023-07-16 19:20:11
• 合計ジャッジ時間: 22,538 ms
• ジャッジサーバーID （参考情報）: judge11 / judge12

ファイルパターン	結果
other	AC * 100

コンパイルメッセージ

warning: variable `max_enemy` is assigned to, but never used
   --> Main.rs:259:13
    |
259 |     let mut max_enemy = None;
    |             ^^^^^^^^^
    |
    = note: consider using `_max_enemy` instead
    = note: `#[warn(unused_variables)]` on by default

warning: value assigned to `max_enemy` is never read
   --> Main.rs:320:29
    |
320 | ...                   max_enemy = Some(enemy);
    |                       ^^^^^^^^^
    |
    = help: maybe it is overwritten before being read?
    = note: `#[warn(unused_assignments)]` on by default

warning: variable does not need to be mutable
   --> Main.rs:57:7
    |
57  |         let mut it = line.split_whitespace();
    |             ----^^
    |             |
    |             help: remove this `mut`
...
152 |     let probs = read!([i8]);
    |                 ----------- in this macro invocation
    |
    = note: `#[warn(unused_mut)]` on by default
    = note: this warning originates in the macro `read` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: constant `SEED` is never used
   --> Main.rs:133:7
    |
133 | const SEED: u32 = 890482;
    |       ^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: constant `TIME_LIMIT` is never used
   --> Main.rs:134:7
    |
134 | const TIME_LIMIT: f64 = 1.9;
    |       ^^^^^^^^^^

warning: function `read_probs` is never used
   --> Main.rs:151:4
    |
151 | fn read_probs() -> Vec<i8> {
    |    ^^^^^^^^^^

warning: 6 warnings emitted

ソースコード

//--------------------------------------------------------------------------------

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(feature = "single_testcase")]
        {
            eprint!("[line:{}] ", line!());
            eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
        }
    }
}

fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

//--------------------------------------------------------------------------------
// https://atcoder.jp/contests/intro-heuristics/submissions/14832097
// let D = read!(usize);
// let c = read!([i64]);
// let s = read!([i64]; D);
// let (n, m) = read!(i32, i32);

#[allow(dead_code)]
fn readln() -> String {
    let mut line = String::new();
    ::std::io::stdin()
        .read_line(&mut line)
        .unwrap_or_else(|e| panic!("{}", e));
    line
}

#[allow(unused_macros)]
macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}

macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}

//--------------------------------------------------------------------------------
// https://atcoder.jp/contests/hokudai-hitachi2017-1/submissions/1797182
// u32 -> usize

pub struct XorShift {
    pub x: [usize; 4],
}

impl XorShift {
    pub fn new(mut seed: usize) -> XorShift {
        let mut x = [0; 4];
        for i in 0..4 {
            seed = 1812433253usize
                .wrapping_mul(seed ^ (seed >> 30))
                .wrapping_add(i as usize);
            x[i] = seed;
        }
        XorShift { x }
    }
    pub fn next_usize(&mut self) -> usize {
        let t = self.x[0] ^ (self.x[0] << 11);
        for i in 0..3 {
            self.x[i] = self.x[i + 1]
        }
        self.x[3] = self.x[3] ^ (self.x[3] >> 19) ^ t ^ (t >> 8);
        self.x[3]
    }
    /// [0, n)
    pub fn next(&mut self, n: usize) -> usize {
        loop {
            let t = self.next_usize();
            let r = t % n;
            if (t - r).checked_add(n).is_some() {
                return r;
            }
        }
    }
    pub fn shuffle<T>(&mut self, a: &mut [T]) {
        for i in 0..a.len() {
            let j = i + self.next(a.len() - i) as usize;
            a.swap(i, j);
        }
    }
}

//--------------------------------------------------------------------------------

const SEED: u32 = 890482;
const TIME_LIMIT: f64 = 1.9;

const INF: usize = 1_000_000_000;

const NUM_TURNS: usize = 1000;
const X: usize = 25;
const Y: usize = 60;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Enemy {
    x: usize,
    y: usize,
    init_hp: i32,
    hp: i32,
    power: i32,
}

fn read_probs() -> Vec<i8> {
    let probs = read!([i8]);
    probs
}

fn read_input() -> Option<Vec<Enemy>> {
    let n = read!(i8);
    if n == -1 {
        None
    } else {
        let mut enemys = vec![];
        for _ in 0..n {
            let (init_hp, power, x) = read!(i32, i32, usize);
            enemys.push(Enemy { x, y: Y - 1, init_hp, hp: init_hp, power});
        }
        Some(enemys)
    }
}

#[derive(Debug)]
struct Player {
    x: usize,
    y: usize,
    score: i32,
    power: i32,
    level: i32,
}

#[derive(Debug)]
struct State {
    board: [[Option<Enemy>; X]; Y],
    player: Player,
}

impl State {
    fn new() -> Self {
        let board = [[None; X]; Y];
        let player = Player { x: X / 2, y: 0, score: 0, power: 0, level: 1 };
        Self { board, player }
    }

    fn update_before(&mut self, enemys: Vec<Enemy>) -> bool {
        // 敵機の更新
        for y in 0..Y - 1 {
            for x in 0..X {
                self.board[y][x] = self.board[y+1][x];
                if let Some(enemy) = &mut self.board[y][x] {
                    enemy.y -= 1;
                }
            }
        }
        for x in 0..X {
            self.board[Y-1][x] = None;
        }
        for enemy in enemys.into_iter() {
            self.board[Y-1][enemy.x] = Some(enemy);
        }

        if let Some(_enemy) = self.board[self.player.y][self.player.x] {
            false
        } else {
            true
        }
    }

    fn update_after(&mut self, command: char) {
        // 移動
        if command == 'L' {
            if self.player.x == 0 {
                self.player.x = X - 1;
            } else {
                self.player.x -= 1;
            }
        } else if command == 'R' {
            if self.player.x == X - 1 {
                self.player.x = 0;
            } else {
                self.player.x += 1;
            }
        } else if command == 'S' {
            // Stay
        } else {
            unreachable!();
        }

        // 攻撃
        for y in 1..Y {
            if let Some(enemy) = &mut self.board[y][self.player.x] {
                debug!(enemy);
                enemy.hp -= self.player.level;
                if enemy.hp <= 0 {
                    // 破壊した
                    self.player.score += enemy.init_hp;
                    self.player.power += enemy.power;
                    self.player.level = 1 + self.player.power / 100;
                    self.board[y][self.player.x] = None;
                }

                break;
            }
        }

    }
}

fn solve(state: &State, turn: usize) -> char {
    let mut max_eval_score = 0.0;
    let mut max_command = 'S';
    let mut max_enemy = None;

    for x in 0..X {
        let mut arrive_dturn = INF;
        let mut command = 'S';
        if x == state.player.x {
            arrive_dturn = 0;
            command = 'S';
        } else {
            let mut min_dturn = INF;
            let mut min_command = 'S';
            for &dx in [!0, 1].iter() {
                let mut now_x = state.player.x;
                let mut cmd = 'S';
                for dturn in 1..=NUM_TURNS - turn {
                    let next_x = now_x.wrapping_add(dx) % X;
                    let no_conflict_0 = dturn - 1 >= Y || state.board[dturn - 1][next_x] == None;
                    let no_conflict_1 = dturn >= Y || (state.board[dturn][next_x] == None || state.board[dturn][next_x].unwrap().hp <= state.player.level);
                    if no_conflict_0 && no_conflict_1 {
                        now_x = next_x;
                    } 

                    if dturn == 1 {
                        if no_conflict_0 && no_conflict_1 {
                            cmd = if dx == !0 {
                                'L'
                            } else {
                                'R'
                            };
                        } else {
                            cmd = 'S';
                        }
                    }

                    if now_x == x {
                        if dturn < min_dturn {
                            min_dturn = dturn;
                            min_command = cmd;
                        }
                        break;
                    }
                }
            }
            if min_dturn != INF {
                arrive_dturn = min_dturn;
                command = min_command;
            }
        }

        // debug!(x, arrive_dturn, command);
        if arrive_dturn < Y {
            let t = turn as f64 / NUM_TURNS as f64;
            for y in arrive_dturn..Y {
                if let Some(enemy) = state.board[y][x] {
                    if (enemy.hp + state.player.level - 1) / state.player.level <= (y - arrive_dturn) as i32 {
                        // 破壊できる
                        let destroy_dturn = arrive_dturn as i32 + (enemy.hp + state.player.level - 1) / state.player.level;
                        let eval_score = (t * enemy.init_hp as f64 + (1.0 - t) * (enemy.power * enemy.power) as f64 / 10000.0) / destroy_dturn as f64;
                        if eval_score > max_eval_score {
                            max_eval_score = eval_score;
                            max_command = command;
                            max_enemy = Some(enemy);
                        }
                    }
                
                    break;
                }
            }
        }
    }

    if let Some(_enemy) = state.board[1][state.player.x] {
        let lx = state.player.x.wrapping_add(!0) % X;
        if state.board[0][lx] == None && state.board[1][lx] == None {
            max_command = 'L';
        } else {
            max_command = 'R';
        }
    }
    debug!(max_eval_score, max_command, max_enemy);

    max_command
}

fn main() {
    get_time();

    #[cfg(feature = "single_testcase")]
    read_probs();

    let mut state = State::new();

    for turn in 1..=NUM_TURNS {
        // if turn == 5 {
        //     break;
        // }
        // debug!(state.board[2]);
        // debug!(state.board[1]);
        // debug!(state.board[0]);
        let enemys = read_input();
        match enemys {
            Some(enemys) => {
                let ok = state.update_before(enemys);
                if !ok {
                    debug!(turn);
                    break;
                }

                debug!(turn, state.player);
                debug!(state.board[0]);
                debug!(state.board[1]);

                let command = solve(&state, turn);
                eprintln!("{}", command);
                println!("{}", command);
                state.update_after(command);
            },
            None => break,
        }
    }

    debug!(state.player.score);

    eprintln!("time_elapsed: {:.3}", get_time());
}