#878673 (Rust) No.5014 セクスタプル (reactive)

提出ソース

結果

問題	No.5014 セクスタプル (reactive)
ユーザー	r3yohei
提出日時	2023-06-08 00:10:12
言語	Rust (1.77.0)
結果	AC
実行時間	340 ms / 2,000 ms
コード長	10,606 bytes
コンパイル時間	2,907 ms
コンパイル使用メモリ	170,416 KB
実行使用メモリ	24,432 KB
スコア	407,010,604
平均クエリ数	35.00
最終ジャッジ日時	2023-06-08 00:10:59
合計ジャッジ時間	42,028 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	340 ms 23,580 KB
testcase_01	AC	338 ms 23,304 KB
testcase_02	AC	334 ms 23,196 KB
testcase_03	AC	337 ms 23,460 KB
testcase_04	AC	338 ms 23,592 KB
testcase_05	AC	332 ms 23,772 KB
testcase_06	AC	331 ms 23,952 KB
testcase_07	AC	337 ms 23,976 KB
testcase_08	AC	335 ms 23,604 KB
testcase_09	AC	335 ms 23,580 KB
testcase_10	AC	333 ms 24,264 KB
testcase_11	AC	334 ms 23,304 KB
testcase_12	AC	335 ms 24,204 KB
testcase_13	AC	336 ms 24,432 KB
testcase_14	AC	332 ms 23,580 KB
testcase_15	AC	335 ms 23,580 KB
testcase_16	AC	334 ms 23,352 KB
testcase_17	AC	334 ms 24,312 KB
testcase_18	AC	333 ms 23,328 KB
testcase_19	AC	334 ms 23,352 KB
testcase_20	AC	333 ms 23,484 KB
testcase_21	AC	335 ms 23,460 KB
testcase_22	AC	334 ms 23,544 KB
testcase_23	AC	332 ms 24,204 KB
testcase_24	AC	333 ms 24,204 KB
testcase_25	AC	333 ms 24,192 KB
testcase_26	AC	333 ms 24,288 KB
testcase_27	AC	329 ms 23,496 KB
testcase_28	AC	332 ms 23,544 KB
testcase_29	AC	335 ms 23,988 KB
testcase_30	AC	335 ms 23,352 KB
testcase_31	AC	332 ms 23,316 KB
testcase_32	AC	330 ms 23,544 KB
testcase_33	AC	333 ms 23,316 KB
testcase_34	AC	335 ms 23,988 KB
testcase_35	AC	332 ms 23,544 KB
testcase_36	AC	336 ms 23,472 KB
testcase_37	AC	334 ms 23,940 KB
testcase_38	AC	331 ms 23,604 KB
testcase_39	AC	338 ms 24,192 KB
testcase_40	AC	336 ms 23,328 KB
testcase_41	AC	330 ms 23,340 KB
testcase_42	AC	332 ms 23,568 KB
testcase_43	AC	333 ms 24,204 KB
testcase_44	AC	333 ms 24,312 KB
testcase_45	AC	333 ms 24,288 KB
testcase_46	AC	331 ms 23,988 KB
testcase_47	AC	332 ms 23,544 KB
testcase_48	AC	332 ms 23,580 KB
testcase_49	AC	331 ms 23,592 KB
testcase_50	AC	333 ms 23,544 KB
testcase_51	AC	334 ms 24,336 KB
testcase_52	AC	336 ms 23,784 KB
testcase_53	AC	333 ms 23,940 KB
testcase_54	AC	332 ms 23,340 KB
testcase_55	AC	333 ms 24,348 KB
testcase_56	AC	333 ms 24,300 KB
testcase_57	AC	331 ms 23,760 KB
testcase_58	AC	332 ms 23,928 KB
testcase_59	AC	335 ms 23,544 KB
testcase_60	AC	333 ms 23,928 KB
testcase_61	AC	333 ms 23,568 KB
testcase_62	AC	331 ms 24,276 KB
testcase_63	AC	334 ms 23,316 KB
testcase_64	AC	335 ms 23,472 KB
testcase_65	AC	336 ms 23,976 KB
testcase_66	AC	333 ms 23,472 KB
testcase_67	AC	331 ms 24,204 KB
testcase_68	AC	332 ms 23,940 KB
testcase_69	AC	334 ms 24,216 KB
testcase_70	AC	336 ms 24,348 KB
testcase_71	AC	333 ms 23,328 KB
testcase_72	AC	337 ms 23,340 KB
testcase_73	AC	333 ms 23,988 KB
testcase_74	AC	331 ms 23,352 KB
testcase_75	AC	331 ms 24,300 KB
testcase_76	AC	332 ms 23,352 KB
testcase_77	AC	336 ms 24,216 KB
testcase_78	AC	336 ms 23,328 KB
testcase_79	AC	334 ms 23,352 KB
testcase_80	AC	332 ms 24,276 KB
testcase_81	AC	332 ms 23,472 KB
testcase_82	AC	337 ms 23,784 KB
testcase_83	AC	334 ms 23,568 KB
testcase_84	AC	332 ms 23,316 KB
testcase_85	AC	335 ms 23,940 KB
testcase_86	AC	328 ms 23,568 KB
testcase_87	AC	332 ms 24,132 KB
testcase_88	AC	333 ms 23,616 KB
testcase_89	AC	334 ms 23,988 KB
testcase_90	AC	333 ms 24,312 KB
testcase_91	AC	332 ms 23,568 KB
testcase_92	AC	331 ms 23,472 KB
testcase_93	AC	335 ms 23,352 KB
testcase_94	AC	333 ms 23,364 KB
testcase_95	AC	333 ms 23,760 KB
testcase_96	AC	333 ms 23,592 KB
testcase_97	AC	333 ms 23,604 KB
testcase_98	AC	333 ms 24,000 KB
testcase_99	AC	335 ms 24,264 KB

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

ソースコード

raw source code

#![allow(non_snake_case, unused)]

use std::io::*;
use std::{collections::*, fmt::format};
use std::{cmp::*, vec};
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; // 全体の制限時間

// 入力を受け取る
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 + 1, p % BOARD_SIZE + 1);
        stdout().flush().unwrap();
    }

    eprintln!("=== Monte Carlo tree search ===");
    eprintln!("time: {}", get_time());
}

yukicoder

結果

テストケース

ソースコード