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

提出ソース

結果

問題	No.5017 Tool-assisted Shooting
ユーザー	shamio
提出日時	2023-07-16 17:40:05
言語	Rust (1.77.0)
結果	AC
実行時間	129 ms / 2,000 ms
コード長	10,649 bytes
コンパイル時間	6,229 ms
コンパイル使用メモリ	213,344 KB
実行使用メモリ	24,444 KB
スコア	2,053,914
平均クエリ数	949.13
最終ジャッジ日時	2023-07-16 17:40:26
合計ジャッジ時間	20,999 ms
ジャッジサーバーID （参考情報）	judge14 / judge16
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	129 ms 24,012 KB
testcase_01	AC	99 ms 24,048 KB
testcase_02	AC	96 ms 23,184 KB
testcase_03	AC	94 ms 24,024 KB
testcase_04	AC	99 ms 23,652 KB
testcase_05	AC	99 ms 23,628 KB
testcase_06	AC	99 ms 23,352 KB
testcase_07	AC	98 ms 24,336 KB
testcase_08	AC	98 ms 23,376 KB
testcase_09	AC	98 ms 23,988 KB
testcase_10	AC	100 ms 23,352 KB
testcase_11	AC	98 ms 23,496 KB
testcase_12	AC	97 ms 23,796 KB
testcase_13	AC	97 ms 23,376 KB
testcase_14	AC	99 ms 23,556 KB
testcase_15	AC	96 ms 23,388 KB
testcase_16	AC	96 ms 23,628 KB
testcase_17	AC	97 ms 23,424 KB
testcase_18	AC	99 ms 23,328 KB
testcase_19	AC	98 ms 23,652 KB
testcase_20	AC	98 ms 23,340 KB
testcase_21	AC	97 ms 23,592 KB
testcase_22	AC	98 ms 23,856 KB
testcase_23	AC	103 ms 23,376 KB
testcase_24	AC	90 ms 23,496 KB
testcase_25	AC	101 ms 24,372 KB
testcase_26	AC	82 ms 23,352 KB
testcase_27	AC	98 ms 23,664 KB
testcase_28	AC	99 ms 23,340 KB
testcase_29	AC	99 ms 23,796 KB
testcase_30	AC	98 ms 23,832 KB
testcase_31	AC	99 ms 23,640 KB
testcase_32	AC	99 ms 23,628 KB
testcase_33	AC	100 ms 24,396 KB
testcase_34	AC	62 ms 23,976 KB
testcase_35	AC	99 ms 23,604 KB
testcase_36	AC	98 ms 24,348 KB
testcase_37	AC	98 ms 23,988 KB
testcase_38	AC	95 ms 23,544 KB
testcase_39	AC	56 ms 24,276 KB
testcase_40	AC	98 ms 23,592 KB
testcase_41	AC	98 ms 23,388 KB
testcase_42	AC	100 ms 24,348 KB
testcase_43	AC	99 ms 24,276 KB
testcase_44	AC	99 ms 23,964 KB
testcase_45	AC	49 ms 23,496 KB
testcase_46	AC	95 ms 24,444 KB
testcase_47	AC	98 ms 23,592 KB
testcase_48	AC	94 ms 23,592 KB
testcase_49	AC	99 ms 23,592 KB
testcase_50	AC	98 ms 24,360 KB
testcase_51	AC	95 ms 24,348 KB
testcase_52	AC	103 ms 23,988 KB
testcase_53	AC	97 ms 23,676 KB
testcase_54	AC	95 ms 23,328 KB
testcase_55	AC	99 ms 23,832 KB
testcase_56	AC	100 ms 23,340 KB
testcase_57	AC	77 ms 23,340 KB
testcase_58	AC	99 ms 23,616 KB
testcase_59	AC	93 ms 23,328 KB
testcase_60	AC	99 ms 23,508 KB
testcase_61	AC	97 ms 23,652 KB
testcase_62	AC	99 ms 23,676 KB
testcase_63	AC	99 ms 23,340 KB
testcase_64	AC	92 ms 23,340 KB
testcase_65	AC	101 ms 23,388 KB
testcase_66	AC	97 ms 23,508 KB
testcase_67	AC	99 ms 23,664 KB
testcase_68	AC	99 ms 23,640 KB
testcase_69	AC	76 ms 23,652 KB
testcase_70	AC	98 ms 23,496 KB
testcase_71	AC	92 ms 23,964 KB
testcase_72	AC	95 ms 23,676 KB
testcase_73	AC	99 ms 23,352 KB
testcase_74	AC	98 ms 24,192 KB
testcase_75	AC	97 ms 24,060 KB
testcase_76	AC	99 ms 24,276 KB
testcase_77	AC	97 ms 23,508 KB
testcase_78	AC	99 ms 23,508 KB
testcase_79	AC	99 ms 23,388 KB
testcase_80	AC	88 ms 23,508 KB
testcase_81	AC	96 ms 23,388 KB
testcase_82	AC	86 ms 23,388 KB
testcase_83	AC	98 ms 23,376 KB
testcase_84	AC	99 ms 24,000 KB
testcase_85	AC	72 ms 23,376 KB
testcase_86	AC	97 ms 24,072 KB
testcase_87	AC	97 ms 23,376 KB
testcase_88	AC	102 ms 23,592 KB
testcase_89	AC	99 ms 23,544 KB
testcase_90	AC	99 ms 23,784 KB
testcase_91	AC	100 ms 23,664 KB
testcase_92	AC	100 ms 23,376 KB
testcase_93	AC	98 ms 23,328 KB
testcase_94	AC	82 ms 24,312 KB
testcase_95	AC	64 ms 24,084 KB
testcase_96	AC	101 ms 23,412 KB
testcase_97	AC	98 ms 23,976 KB
testcase_98	AC	99 ms 24,336 KB
testcase_99	AC	106 ms 24,000 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused variable: `y`
   --> Main.rs:357:13
    |
357 |         for y in (0..Y).rev() {
    |             ^ help: if this is intentional, prefix it with an underscore: `_y`
    |
    = note: `#[warn(unused_variables)]` 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: 5 warnings emitted

ソースコード

raw source code

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

#[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;
    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 {
            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 = enemy.init_hp / destroy_dturn;
                        if eval_score > max_eval_score {
                            max_eval_score = eval_score;
                            max_command = command;
                            max_enemy = Some(enemy);
                        }
                    }
                
                    break;
                }
            }
        }
    }

    if max_enemy == None {
        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!(turn, state.player);
        for y in (0..Y).rev() {
            debug!(y, state.board[y]);
            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;
                }
                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());
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード