結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 tipstar0125
|
| 提出日時 | 2023-08-01 18:50:57 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,290 bytes |
| コンパイル時間 | 2,150 ms |
| コンパイル使用メモリ | 163,028 KB |
| 実行使用メモリ | 24,540 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-08-01 18:54:41 |
| 合計ジャッジ時間 | 219,661 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | TLE | - |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
| testcase_30 | TLE | - |
| testcase_31 | TLE | - |
| testcase_32 | TLE | - |
| testcase_33 | TLE | - |
| testcase_34 | TLE | - |
| testcase_35 | TLE | - |
| testcase_36 | TLE | - |
| testcase_37 | TLE | - |
| testcase_38 | TLE | - |
| testcase_39 | TLE | - |
| testcase_40 | TLE | - |
| testcase_41 | TLE | - |
| testcase_42 | TLE | - |
| testcase_43 | TLE | - |
| testcase_44 | TLE | - |
| testcase_45 | TLE | - |
| testcase_46 | TLE | - |
| testcase_47 | TLE | - |
| testcase_48 | TLE | - |
| testcase_49 | TLE | - |
| testcase_50 | TLE | - |
| testcase_51 | TLE | - |
| testcase_52 | TLE | - |
| testcase_53 | TLE | - |
| testcase_54 | TLE | - |
| testcase_55 | TLE | - |
| testcase_56 | TLE | - |
| testcase_57 | TLE | - |
| testcase_58 | TLE | - |
| testcase_59 | TLE | - |
| testcase_60 | TLE | - |
| testcase_61 | TLE | - |
| testcase_62 | TLE | - |
| testcase_63 | TLE | - |
| testcase_64 | TLE | - |
| testcase_65 | TLE | - |
| testcase_66 | TLE | - |
| testcase_67 | TLE | - |
| testcase_68 | TLE | - |
| testcase_69 | TLE | - |
| testcase_70 | TLE | - |
| testcase_71 | TLE | - |
| testcase_72 | TLE | - |
| testcase_73 | TLE | - |
| testcase_74 | TLE | - |
| testcase_75 | TLE | - |
| testcase_76 | TLE | - |
| testcase_77 | TLE | - |
| testcase_78 | TLE | - |
| testcase_79 | TLE | - |
| testcase_80 | TLE | - |
| testcase_81 | TLE | - |
| testcase_82 | TLE | - |
| testcase_83 | TLE | - |
| testcase_84 | TLE | - |
| testcase_85 | TLE | - |
| testcase_86 | TLE | - |
| testcase_87 | TLE | - |
| testcase_88 | TLE | - |
| testcase_89 | TLE | - |
| testcase_90 | TLE | - |
| testcase_91 | TLE | - |
| testcase_92 | TLE | - |
| testcase_93 | TLE | - |
| testcase_94 | TLE | - |
| testcase_95 | TLE | - |
| testcase_96 | TLE | - |
| testcase_97 | TLE | - |
| testcase_98 | TLE | - |
| testcase_99 | TLE | - |
ソースコード
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(clippy::type_complexity)]
#![allow(clippy::needless_range_loop)]
#![allow(dead_code)]
use std::{
cmp::Reverse,
collections::{BTreeMap, BTreeSet, BinaryHeap, VecDeque},
};
mod rnd {
static mut S: usize = 0;
static MAX: usize = 1e9 as usize;
#[inline]
pub fn init(seed: usize) {
unsafe {
if seed == 0 {
let t = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.unwrap()
.as_secs() as usize;
S = t
} else {
S = seed;
}
}
}
#[inline]
pub fn gen() -> usize {
unsafe {
if S == 0 {
init(0);
}
S ^= S << 7;
S ^= S >> 9;
S
}
}
#[inline]
pub fn gen_range(a: usize, b: usize) -> usize {
gen() % (b - a) + a
}
#[inline]
pub fn gen_bool() -> bool {
gen() & 1 == 1
}
#[inline]
pub fn gen_range_isize(a: usize) -> isize {
let mut x = (gen() % a) as isize;
if gen_bool() {
x *= -1;
}
x
}
#[inline]
pub fn gen_range_neg_wrapping(a: usize) -> usize {
let mut x = gen() % a;
if gen_bool() {
x = x.wrapping_neg();
}
x
}
#[inline]
pub fn gen_float() -> f64 {
((gen() % MAX) as f64) / MAX as f64
}
}
#[derive(Debug, Clone)]
struct TimeKeeper {
start_time: std::time::Instant,
time_threshold: f64,
}
impl TimeKeeper {
fn new(time_threshold: f64) -> Self {
TimeKeeper {
start_time: std::time::Instant::now(),
time_threshold,
}
}
#[inline]
fn isTimeOver(&self) -> bool {
let elapsed_time = self.start_time.elapsed().as_nanos() as f64 * 1e-9;
#[cfg(feature = "local")]
{
elapsed_time * 1.5 >= self.time_threshold
}
#[cfg(not(feature = "local"))]
{
elapsed_time >= self.time_threshold
}
}
#[inline]
fn get_time(&self) -> f64 {
let elapsed_time = self.start_time.elapsed().as_nanos() as f64 * 1e-9;
#[cfg(feature = "local")]
{
elapsed_time * 1.5
}
#[cfg(not(feature = "local"))]
{
elapsed_time
}
}
}
const H: usize = 60;
const W: usize = 25;
const TURN: usize = 1000;
const INF: isize = 1 << 60;
#[derive(Debug, Clone, Eq, PartialEq)]
struct Player {
x: usize,
y: usize,
}
impl Player {
fn new() -> Self {
Player { x: 12, y: 0 }
}
fn move_(&mut self, action: isize) {
self.y += 1;
self.x = (W as isize + action + self.x as isize) as usize % W;
}
}
#[derive(Debug, Clone, Eq, PartialEq)]
struct Enemy {
hp: isize,
power: isize,
init_hp: isize,
x: usize,
y: usize,
}
impl Enemy {
fn new(init_hp: isize, power: isize, x: usize, y: usize) -> Self {
Enemy {
hp: init_hp,
power,
init_hp,
x,
y,
}
}
}
#[derive(Debug, Clone, Eq)]
struct State {
player: Player,
S: isize,
score: isize,
evaluated_score: isize,
enemies: Vec<VecDeque<Enemy>>,
turn: usize,
first_action: isize,
is_dead: bool,
}
impl State {
fn new() -> Self {
State {
player: Player::new(),
S: 0,
score: 0,
evaluated_score: 0,
enemies: vec![VecDeque::new(); W],
turn: 0,
first_action: 0,
is_dead: false,
}
}
fn update_enemy(&mut self, n: usize) {
let y = H + self.turn;
for _ in 0..n {
let v: Vec<isize> = read_vec();
let h = v[0];
let p = v[1];
let x = v[2] as usize;
let enemy = Enemy::new(h, p, x, y);
self.enemies[x].push_back(enemy);
}
for x in 0..W {
if self.enemies[x].is_empty() {
continue;
}
if y - self.enemies[x][0].y == H {
self.enemies[x].pop_front();
}
}
}
fn get_level(&self) -> isize {
1 + self.S / 100
}
fn advance(&mut self, action: isize) {
self.player.move_(action);
self.attack();
self.turn += 1;
}
fn attack(&mut self) {
if self.enemies[self.player.x].is_empty() {
return;
}
let level = self.get_level();
let enemy = &self.enemies[self.player.x][0];
if enemy.y == self.player.y {
self.is_dead = true;
return;
}
if enemy.y == self.player.y + 1 && enemy.hp > level {
self.is_dead = true;
return;
}
if enemy.hp <= level {
self.score += enemy.init_hp;
self.S += enemy.power;
self.enemies[self.player.x].pop_front();
} else {
self.enemies[self.player.x][0].hp -= level;
}
}
fn evaluate_score(&mut self) {
self.evaluated_score = self.S;
}
fn is_done(&self) -> bool {
self.turn == TURN
}
fn output(&self, action: isize) {
if action == 0 {
println!("S");
} else if action == -1 {
println!("L");
} else {
println!("R");
}
}
}
impl std::cmp::PartialEq for State {
fn eq(&self, other: &Self) -> bool {
self.evaluated_score == other.evaluated_score
}
}
impl std::cmp::PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
if self.evaluated_score == other.evaluated_score {
Some(std::cmp::Ordering::Equal)
} else if self.evaluated_score > other.evaluated_score {
Some(std::cmp::Ordering::Greater)
} else if self.evaluated_score < other.evaluated_score {
Some(std::cmp::Ordering::Less)
} else {
None
}
}
}
impl std::cmp::Ord for State {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
if self.evaluated_score == other.evaluated_score {
std::cmp::Ordering::Equal
} else if self.evaluated_score > other.evaluated_score {
std::cmp::Ordering::Greater
} else {
std::cmp::Ordering::Less
}
}
}
fn beam_search_action(state: &State, beam_width: usize, time_threshold: f64) -> State {
let mut now_beam = BinaryHeap::new();
let mut best_state = state;
now_beam.push(state.clone());
let time_keeper = TimeKeeper::new(time_threshold);
for t in 0.. {
let mut next_beam = BinaryHeap::new();
for _ in 0..beam_width {
if now_beam.is_empty() {
break;
}
let now_state = now_beam.pop().unwrap();
let mut next_state_front = now_state.clone();
let mut next_state_left = now_state.clone();
let mut next_state_right = now_state.clone();
next_state_front.advance(0);
next_state_front.evaluate_score();
next_state_left.advance(-1);
next_state_left.evaluate_score();
next_state_right.advance(1);
next_state_right.evaluate_score();
if t == 0 {
next_state_front.first_action = 0;
next_state_left.first_action = -1;
next_state_right.first_action = 1;
}
if !next_state_front.is_dead {
next_beam.push(next_state_front);
}
if !next_state_left.is_dead {
next_beam.push(next_state_left);
}
if !next_state_right.is_dead {
next_beam.push(next_state_right);
}
if time_keeper.isTimeOver() {
break;
}
}
now_beam = next_beam;
best_state = now_beam.peek().unwrap();
if best_state.is_done() || time_keeper.isTimeOver() {
break;
}
}
// best_state.first_action
best_state.clone()
}
#[derive(Default)]
struct Solver {}
impl Solver {
fn solve(&mut self) {
let mut state = State::new();
#[cfg(feature = "local")]
{
eprintln!("Local Mode");
let _: Vec<usize> = read_vec();
}
let start = std::time::Instant::now();
let time_threshold = 1.5 * 1e-3; // [sec]
while !state.is_done() {
let N: isize = read();
if N == -1 {
return;
}
state.update_enemy(N as usize);
let s = beam_search_action(&state, 10000, time_threshold);
let action = s.first_action;
state.advance(action);
state.output(action);
}
eprintln!("Score: {}", state.score);
eprintln!("S: {}", state.S);
#[allow(unused_mut, unused_assignments)]
let mut elapsed_time = start.elapsed().as_micros() as f64 * 1e-6;
#[cfg(feature = "local")]
{
eprintln!("Local Mode");
elapsed_time *= 1.5;
}
eprintln!("Elapsed time: {}sec", elapsed_time);
}
}
#[macro_export]
macro_rules! max {
($x: expr) => ($x);
($x: expr, $( $y: expr ),+) => {
std::cmp::max($x, max!($( $y ),+))
}
}
#[macro_export]
macro_rules! min {
($x: expr) => ($x);
($x: expr, $( $y: expr ),+) => {
std::cmp::min($x, min!($( $y ),+))
}
}
fn main() {
std::thread::Builder::new()
.stack_size(128 * 1024 * 1024)
.spawn(|| Solver::default().solve())
.unwrap()
.join()
.unwrap();
}
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}