結果
| 問題 | No.5014 セクスタプル (reactive) |
| ユーザー |
 r3yohei
|
| 提出日時 | 2023-06-08 00:04:44 |
| 言語 | Rust (1.77.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 14,031 bytes |
| コンパイル時間 | 3,085 ms |
| コンパイル使用メモリ | 168,208 KB |
| 実行使用メモリ | 24,432 KB |
| スコア | 0 |
| 平均クエリ数 | 3.20 |
| 最終ジャッジ日時 | 2023-06-08 00:05:08 |
| 合計ジャッジ時間 | 19,024 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | RE | - |
| 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 | RE | - |
| testcase_40 | RE | - |
| testcase_41 | RE | - |
| testcase_42 | RE | - |
| testcase_43 | RE | - |
| testcase_44 | RE | - |
| testcase_45 | RE | - |
| testcase_46 | RE | - |
| 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 | RE | - |
| testcase_63 | RE | - |
| testcase_64 | RE | - |
| testcase_65 | RE | - |
| testcase_66 | RE | - |
| testcase_67 | RE | - |
| testcase_68 | RE | - |
| testcase_69 | RE | - |
| testcase_70 | RE | - |
| testcase_71 | RE | - |
| testcase_72 | RE | - |
| testcase_73 | RE | - |
| 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 | RE | - |
| testcase_93 | RE | - |
| testcase_94 | RE | - |
| testcase_95 | RE | - |
| testcase_96 | RE | - |
| testcase_97 | RE | - |
| testcase_98 | RE | - |
| testcase_99 | RE | - |
ソースコード
#![allow(non_snake_case, unused)]
use std::io::*;
use std::{collections::*, fmt::format};
use std::{cmp::*, vec};
use crate::input::{*, marker::*};
use crate::rand::Xoshiro256;
const TURN: usize = 35; // 操作回数
const N: usize = 36; // セルの数 (=操作回数-1)
const PLAYOUT_EPOCH: usize = 10; // 期待値計算のためにプレイアウトする回数
const NUM_DICE: usize = 6; // 操作1回当りのダイスの数
const BOARD_SIZE: usize = 6; // ダイスを配置するセルのサイズ
const TL: f64 = 1.98; // 全体の制限時間
pub mod input {
use std::{
cell::RefCell,
fmt::Debug,
io::{stdin, BufRead, BufReader, Stdin},
str::{FromStr, SplitWhitespace},
};
thread_local!(
pub static STDIN_SOURCE: RefCell<Source> = RefCell::new(Source {
stdin: BufReader::new(stdin()),
tokens: "".split_whitespace(),
});
);
pub struct Source {
stdin: BufReader<Stdin>,
tokens: SplitWhitespace<'static>,
}
impl Source {
pub fn next_token(&mut self) -> Option<&str> {
self.tokens.next().or_else(|| {
let mut input = String::new();
self.stdin.read_line(&mut input).unwrap();
self.tokens = Box::leak(input.into_boxed_str()).split_whitespace();
self.tokens.next()
})
}
}
#[macro_export]
macro_rules! read_value {
(from $s:expr, [$t:tt; $n:expr]) => {
(0..$n).map(|_| $crate::read_value!(from $s, $t)).collect::<Vec<_>>()
};
(from $s:expr, [$t:tt]) => {
let n = $crate::read_value!(from $s, usize);
$crate::read_value!(from $s, [$t; n])
};
(from $s:expr, $t:ty) => {
<$t as $crate::input::Readable>::read(&mut $s)
};
(from $s:expr, $($t:tt),* $(,)?) => {
($($crate::read_value!(from $s, $t)),*)
};
($($r:tt)*) => {
$crate::input::STDIN_SOURCE.with(|s| {
let mut s = s.borrow_mut();
$crate::read_value!(from s, $($r)*)
})
}
}
#[macro_export]
macro_rules! input {
() => {
};
($x:tt: $t:tt, $($r:tt)*) => {
let $x = $crate::read_value!($t);
$crate::input!($($r)*);
};
(mut $x:tt: $t:tt, $($r:tt)*) => {
let mut $x = $crate::read_value!($t);
$crate::input!($($r)*);
};
(from $s:expr, $x:tt, $t:tt, $($r:tt)*) => {
let $x = $crate::read_value!(from $s, $t);
$crate::input!(from $s, $($r)*);
};
(from $s:expr, mut $x:tt, $t:tt, $($r:tt)*) => {
let mut $x = $crate::read_value!(from $s, $t);
$crate::input!(from $s, $($r)*);
};
($($r:tt)*) => {
$crate::input!($($r)*,);
};
}
pub trait Readable {
type Output;
fn read(source: &mut Source) -> Self::Output;
}
impl<T: FromStr<Err = E>, E: Debug> Readable for T {
type Output = T;
fn read(source: &mut Source) -> T {
source.next_token().unwrap().parse().unwrap()
}
}
pub mod marker {
macro_rules! impl_readable {
($e:ident, $t:ty, $u:ty, $f:expr) => {
pub enum $e {}
impl $crate::input::Readable for $e {
type Output = $t;
fn read(mut source: &mut $crate::input::Source) -> $t {
$f($crate::read_value!(from source, $u))
}
}
};
}
impl_readable!(Usize1, usize, usize, |x| x - 1);
impl_readable!(Isize1, isize, isize, |x| x - 1);
impl_readable!(Chars, Vec<char>, String, |x: String| x.chars().collect());
impl_readable!(Bytes, Vec<u8>, String, |x: String| x.bytes().collect());
}
}
// 入力を受け取る
fn read_buffer() -> Vec<usize> {
let mut input = String::new();
std::io::stdin().read_line(&mut input).expect("Failed to read line.");
let v: Vec<&str> = input.split_whitespace().collect();
return v.iter().map(|&s| s.parse().unwrap()).collect();
}
mod rand {
pub(crate) struct Xoshiro256 {
s0: u64,
s1: u64,
s2: u64,
s3: u64,
}
impl Xoshiro256 {
pub(crate) fn new(mut seed: u64) -> Self {
let s0 = split_mix_64(&mut seed);
let s1 = split_mix_64(&mut seed);
let s2 = split_mix_64(&mut seed);
let s3 = split_mix_64(&mut seed);
Self { s0, s1, s2, s3 }
}
fn next(&mut self) -> u64 {
let result = (self.s1.wrapping_mul(5)).rotate_left(7).wrapping_mul(9);
let t = self.s1 << 17;
self.s2 ^= self.s0;
self.s3 ^= self.s1;
self.s1 ^= self.s2;
self.s0 ^= self.s3;
self.s2 ^= t;
self.s3 = self.s3.rotate_left(45);
result
}
pub(crate) fn gen_usize(&mut self, lower: usize, upper: usize) -> usize {
assert!(lower < upper);
let count = upper - lower;
(self.next() % count as u64) as usize + lower
}
pub(crate) fn gen_i64(&mut self, lower: i64, upper: i64) -> i64 {
assert!(lower < upper);
let count = upper - lower;
(self.next() % count as u64) as i64 + lower
}
pub(crate) fn gen_f64(&mut self) -> f64 {
const UPPER_MASK: u64 = 0x3ff0000000000000;
const LOWER_MASK: u64 = 0xfffffffffffff;
let result = UPPER_MASK | (self.next() & LOWER_MASK);
let result: f64 = unsafe { std::mem::transmute(result) };
result - 1.0
}
pub(crate) fn gen_bool(&mut self, prob: f64) -> bool {
self.gen_f64() < prob
}
}
fn split_mix_64(x: &mut u64) -> u64 {
*x = x.wrapping_add(0x9e3779b97f4a7c15);
let mut z = *x;
z = (z ^ z >> 30).wrapping_mul(0xbf58476d1ce4e5b9);
z = (z ^ z >> 27).wrapping_mul(0x94d049bb133111eb);
z ^ z >> 31
}
}
pub trait ChangeMinMax {
fn change_min(&mut self, v: Self) -> bool;
fn change_max(&mut self, v: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
fn change_min(&mut self, v: T) -> bool {
*self > v && { *self = v; true }
}
fn change_max(&mut self, v: T) -> bool {
*self < v && { *self = v; true }
}
}
pub 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;
}
// ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
#[cfg(feature = "local")]
{
(ms - STIME) * 1.5
}
#[cfg(not(feature = "local"))]
{
(ms - STIME)
}
}
}
#[derive(Clone, Debug)]
struct State {
turn: usize,
dice: Vec<Vec<usize>>, // dice[i][j] := i回目のダイスjの出目
cell: Vec<usize>, // cell[i * BOARD_SIZE + j] := i行j列目に置かれたのが何操作目の出目か
}
impl State {
fn new() -> Self {
let cell = vec![!0; BOARD_SIZE * BOARD_SIZE];
Self { turn: 0, dice: vec![], cell }
}
// 入力から受け取ったダイスをp(0~35)のいずれかの位置に置く
fn place(&mut self, p: usize, input: &Vec<usize>) -> bool {
// 置けるかを判定する
if self.cell[p] != !0 {return false;}
// cell配列で保持する操作はdice配列へのアクセスを容易にするために0-indexとしておくので，turnのインクリメントより先に行う
self.cell[p] = self.turn;
self.turn += 1;
self.dice.push(input.to_vec());
true
}
fn calc_score(&self) -> i64 {
let mut score = 0;
for i in 0..BOARD_SIZE {
// iを行，jを列とみなすのと，iを列，jを行とみなすのを同時にやる
// iを行とみなすとき，i行目について，全ての列に登場する目があるか･全ての列に登場する目で，さらに追加の目があるかを調べる
let mut num_dice_row = vec![0; NUM_DICE];
let mut forbidden_set_row = HashSet::new();
// iを列とみなすとき，i列目について，全ての行に登場する目があるか･全ての行に登場する目で，さらに追加の目があるかを調べる
let mut num_dice_col = vec![0; NUM_DICE];
let mut forbidden_set_col = HashSet::new();
for j in 0..BOARD_SIZE {
// iを行とみなすとき
let dice_ij: &Vec<usize> = &self.dice[self.cell[i * BOARD_SIZE + j]];
let mut num_dice_map_row = HashMap::new();
for &d in dice_ij {
*num_dice_map_row.entry(d).or_insert(0) += 1;
}
// セル(i, j)について計上
for d in 1..=6 {
// (i, j)に存在しない目があるかどうかを判定しておく
if let Some(&num_d) = num_dice_map_row.get(&d) {
// あればとりあえず計上
num_dice_row[d - 1] += num_d;
} else {
// なければ無いことを記録
forbidden_set_row.insert(d);
}
}
// iを列とみなすとき
let dice_ji = &self.dice[self.cell[j * BOARD_SIZE + i]];
let mut num_dice_map_col = HashMap::new();
for &d in dice_ji {
*num_dice_map_col.entry(d).or_insert(0) += 1;
}
// セル(i, j)について計上
for d in 1..=6 {
// (i, j)に存在しない目があるかどうかを判定しておく
if let Some(&num_d) = num_dice_map_col.get(&d) {
// あればとりあえず計上
num_dice_col[d - 1] += num_d;
} else {
// なければ無いことを記録
forbidden_set_col.insert(d);
}
}
}
// iを行とみなすとき，各目1~6で，すべての列に含まれるものの数を数え，定義よりその数-3が当該行のスコアとなる
// iを列とみなすときも同じ
for d in 1..=6 {
if !forbidden_set_row.contains(&d) {
score += num_dice_row[d - 1] - 3;
}
if !forbidden_set_col.contains(&d) {
score += num_dice_col[d - 1] - 3;
}
}
}
score
}
}
// 現在の状態をtとして，t+1~最後まで遊んだ時のスコアの期待値が最も高いt+1番目の手を返す
// 現在入力から受け取ったダイスより先のダイスをt+1~TURN個勝手に決めてプレイしまくる
// t+1番目がLの手の平均スコア, t+1がR,...を計算し，最も高いものをt+1番目の手として採用する
fn playout(mut rng: &mut Xoshiro256, state: &State, input: &Vec<usize>) -> usize {
// t番目の手とスコアの期待値のmap
let mut map: HashMap<usize, i64> = HashMap::new();
// t番目の手を固定して，t+1~36までを何回か遊ぶ
let mut empty = vec![];
// 置ける場所を探す
for p in 0..N {
if state.cell[p] == !0 {empty.push(p);}
}
for &p in &empty {
// 各シミュレーションでのスコアを格納する(後で平均を出す)
let mut scores = vec![];
// [ToDo]: ターンが最初の方の時ほど長めにとるよう時間管理する
for _ in 0..PLAYOUT_EPOCH {
// まずはt番目は固定した手を実行
let mut state_tmp = state.clone();
state_tmp.place(p, input);
// 残りターンでダイスを適当に生成し，置くことを繰り返す
for (i, t) in (state_tmp.turn..TURN+1).enumerate() {
let mut sim_empty = vec![];
// 置ける場所を探す
for q in 0..N {
if state_tmp.cell[q] == !0 {sim_empty.push(q);}
}
let sim_p_idx = rng.gen_usize(0, sim_empty.len());
let sim_p = sim_empty[sim_p_idx];
let mut sim_input = vec![];
for _ in 0..NUM_DICE {
sim_input.push(rng.gen_usize(1, 7));
}
state_tmp.place(sim_p, &sim_input);
}
// 終わったらスコア計算
let score = state_tmp.calc_score();
scores.push(score);
}
let mean = scores.iter().sum::<i64>() / scores.len() as i64;
map.insert(p, mean);
}
// mapをソートして最大を取得
let (p_max, _) = map.iter()
.max_by(|a, b| a.1.cmp(&b.1))
.unwrap();
*p_max
}
fn main() {
get_time();
let mut rng = Xoshiro256::new(8192);
let mut state = State::new();
for t in 0..TURN {
// 入力のダイスを受け取る
let input = read_buffer();
// ランダムプレイアウトして，t番目の手を決める
let p = playout(&mut rng, &state, &input);
state.place(p, &input);
// 回答を出力し，フラッシュする
println!("{} {}", p / BOARD_SIZE, p % BOARD_SIZE);
stdout().flush().unwrap();
}
eprintln!("=== Monte Carlo tree search ===");
eprintln!("time: {}", get_time());
}