結果

問題 No.5017 Tool-assisted Shooting
ユーザー shamioshamio
提出日時 2023-07-16 18:04:07
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 10,824 bytes
コンパイル時間 5,601 ms
コンパイル使用メモリ 211,144 KB
実行使用メモリ 24,372 KB
スコア 3,487,022
平均クエリ数 967.02
最終ジャッジ日時 2023-07-16 18:04:28
合計ジャッジ時間 19,916 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 101 ms
23,952 KB
testcase_01 AC 97 ms
23,808 KB
testcase_02 AC 97 ms
23,388 KB
testcase_03 AC 98 ms
23,388 KB
testcase_04 AC 97 ms
23,472 KB
testcase_05 AC 99 ms
23,988 KB
testcase_06 AC 97 ms
23,844 KB
testcase_07 AC 96 ms
23,640 KB
testcase_08 AC 98 ms
23,844 KB
testcase_09 AC 84 ms
23,604 KB
testcase_10 AC 95 ms
23,400 KB
testcase_11 AC 71 ms
24,312 KB
testcase_12 AC 92 ms
23,580 KB
testcase_13 AC 97 ms
23,964 KB
testcase_14 AC 100 ms
24,180 KB
testcase_15 AC 98 ms
24,276 KB
testcase_16 AC 95 ms
23,472 KB
testcase_17 AC 99 ms
24,036 KB
testcase_18 AC 98 ms
23,376 KB
testcase_19 AC 94 ms
24,276 KB
testcase_20 AC 95 ms
23,664 KB
testcase_21 AC 97 ms
23,532 KB
testcase_22 AC 94 ms
23,592 KB
testcase_23 AC 98 ms
23,532 KB
testcase_24 AC 97 ms
23,832 KB
testcase_25 AC 99 ms
24,348 KB
testcase_26 AC 91 ms
23,976 KB
testcase_27 AC 89 ms
23,592 KB
testcase_28 AC 99 ms
23,484 KB
testcase_29 AC 97 ms
23,472 KB
testcase_30 AC 96 ms
24,348 KB
testcase_31 AC 97 ms
23,484 KB
testcase_32 AC 93 ms
24,024 KB
testcase_33 AC 103 ms
24,036 KB
testcase_34 AC 97 ms
23,316 KB
testcase_35 AC 97 ms
23,448 KB
testcase_36 AC 97 ms
23,316 KB
testcase_37 AC 99 ms
24,276 KB
testcase_38 AC 97 ms
23,388 KB
testcase_39 AC 97 ms
24,036 KB
testcase_40 AC 98 ms
24,288 KB
testcase_41 AC 84 ms
23,964 KB
testcase_42 AC 99 ms
24,288 KB
testcase_43 AC 90 ms
24,024 KB
testcase_44 AC 97 ms
23,412 KB
testcase_45 AC 79 ms
23,364 KB
testcase_46 AC 94 ms
23,664 KB
testcase_47 AC 92 ms
23,820 KB
testcase_48 AC 87 ms
24,288 KB
testcase_49 AC 95 ms
23,940 KB
testcase_50 AC 96 ms
23,640 KB
testcase_51 AC 92 ms
23,664 KB
testcase_52 AC 95 ms
23,652 KB
testcase_53 AC 96 ms
23,340 KB
testcase_54 AC 69 ms
23,472 KB
testcase_55 AC 94 ms
23,376 KB
testcase_56 AC 96 ms
23,592 KB
testcase_57 AC 85 ms
24,216 KB
testcase_58 AC 96 ms
23,568 KB
testcase_59 AC 88 ms
23,436 KB
testcase_60 AC 92 ms
24,312 KB
testcase_61 AC 99 ms
23,472 KB
testcase_62 AC 98 ms
23,544 KB
testcase_63 AC 97 ms
23,976 KB
testcase_64 AC 97 ms
24,336 KB
testcase_65 AC 97 ms
23,664 KB
testcase_66 AC 97 ms
24,300 KB
testcase_67 AC 90 ms
23,604 KB
testcase_68 AC 97 ms
24,348 KB
testcase_69 AC 98 ms
24,312 KB
testcase_70 AC 99 ms
23,628 KB
testcase_71 AC 98 ms
24,372 KB
testcase_72 AC 97 ms
23,988 KB
testcase_73 AC 88 ms
24,360 KB
testcase_74 AC 97 ms
23,376 KB
testcase_75 AC 97 ms
23,844 KB
testcase_76 AC 97 ms
23,964 KB
testcase_77 AC 93 ms
24,060 KB
testcase_78 AC 60 ms
23,664 KB
testcase_79 AC 88 ms
23,544 KB
testcase_80 AC 94 ms
23,316 KB
testcase_81 AC 86 ms
23,328 KB
testcase_82 AC 93 ms
23,640 KB
testcase_83 AC 97 ms
24,312 KB
testcase_84 AC 96 ms
23,976 KB
testcase_85 AC 97 ms
23,964 KB
testcase_86 AC 87 ms
23,844 KB
testcase_87 AC 91 ms
23,976 KB
testcase_88 AC 93 ms
23,580 KB
testcase_89 AC 95 ms
23,856 KB
testcase_90 AC 108 ms
23,388 KB
testcase_91 AC 93 ms
23,640 KB
testcase_92 AC 82 ms
23,988 KB
testcase_93 AC 49 ms
23,376 KB
testcase_94 AC 96 ms
23,976 KB
testcase_95 AC 97 ms
23,484 KB
testcase_96 AC 95 ms
23,964 KB
testcase_97 AC 97 ms
23,820 KB
testcase_98 AC 98 ms
23,940 KB
testcase_99 AC 88 ms
23,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `y`
   --> Main.rs:370:21
    |
370 |                 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

ソースコード

diff # 

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

#[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 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!(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);
                for y in (0..Y).rev() {
                    debug!(y, state.board[y]);
                    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());
}
0