結果

問題 No.5017 Tool-assisted Shooting
ユーザー shamioshamio
提出日時 2023-07-16 17:08:09
言語 Rust
(1.77.0)
結果
RE  
実行時間 -
コード長 9,993 bytes
コンパイル時間 6,356 ms
コンパイル使用メモリ 206,532 KB
実行使用メモリ 24,468 KB
スコア 29,950
平均クエリ数 285.21
最終ジャッジ日時 2023-07-16 17:08:28
合計ジャッジ時間 16,307 ms
ジャッジサーバーID
(参考情報)
judge16 / judge14
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 AC 97 ms
24,000 KB
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 AC 97 ms
23,424 KB
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 AC 98 ms
23,592 KB
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 RE -
testcase_61 RE -
testcase_62 AC 96 ms
23,604 KB
testcase_63 RE -
testcase_64 RE -
testcase_65 AC 97 ms
24,348 KB
testcase_66 RE -
testcase_67 RE -
testcase_68 RE -
testcase_69 RE -
testcase_70 RE -
testcase_71 RE -
testcase_72 RE -
testcase_73 AC 97 ms
23,376 KB
testcase_74 RE -
testcase_75 RE -
testcase_76 RE -
testcase_77 RE -
testcase_78 RE -
testcase_79 RE -
testcase_80 RE -
testcase_81 RE -
testcase_82 RE -
testcase_83 RE -
testcase_84 RE -
testcase_85 RE -
testcase_86 RE -
testcase_87 RE -
testcase_88 RE -
testcase_89 RE -
testcase_90 RE -
testcase_91 RE -
testcase_92 AC 97 ms
23,964 KB
testcase_93 RE -
testcase_94 RE -
testcase_95 RE -
testcase_96 RE -
testcase_97 RE -
testcase_98 RE -
testcase_99 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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: 4 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() -> Vec<Enemy> {
    let n = read!(i8);
    if n == -1 {
        vec![]
    } 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});
        }
        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 + 1) / 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_turn = INF;
        let mut command = 'S';
        if x == state.player.x {
            arrive_turn = 0;
            command = 'S';
        } else {
            for &dx in [!0, 1].iter() {
                let mut now_x = state.player.x;
                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 {
                            command = if dx == !0 {
                                'L'
                            } else {
                                'R'
                            };
                        } else {
                            command = 'S';
                        }
                    }

                    if now_x == x {
                        if turn + dturn < arrive_turn {
                            arrive_turn = turn + dturn;
                        }
                        break;
                    }
                }
            }
        }

        if arrive_turn < Y {
            for y in arrive_turn..Y {
                if let Some(enemy) = state.board[y][x] {
                    if (enemy.hp + state.player.level - 1) / state.player.level <= (y - arrive_turn) as i32{
                        // 破壊できる
                        let destroy_dturn = arrive_turn 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 {
        debug!(turn, state.player);
        // debug!(state.board[2]);
        // debug!(state.board[1]);
        // debug!(state.board[0]);
        let enemys = read_input();
        let ok = state.update_before(enemys);
        if !ok {
            debug!(turn);
            break;
        }
        let command = solve(&state, turn);
        eprintln!("{}", command);
        println!("{}", command);
        state.update_after(command);
    }

    debug!(state.player.score);

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