結果

問題 No.5013 セクスタプル (open)
ユーザー r3yoheir3yohei
提出日時 2023-06-05 21:56:12
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,982 ms / 2,000 ms
コード長 13,560 bytes
コンパイル時間 2,326 ms
コンパイル使用メモリ 169,516 KB
実行使用メモリ 4,376 KB
スコア 17,011
最終ジャッジ日時 2023-06-05 21:59:41
合計ジャッジ時間 207,806 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,981 ms
4,368 KB
testcase_01 AC 1,981 ms
4,372 KB
testcase_02 AC 1,981 ms
4,368 KB
testcase_03 AC 1,980 ms
4,368 KB
testcase_04 AC 1,981 ms
4,368 KB
testcase_05 AC 1,981 ms
4,368 KB
testcase_06 AC 1,982 ms
4,368 KB
testcase_07 AC 1,982 ms
4,368 KB
testcase_08 AC 1,981 ms
4,368 KB
testcase_09 AC 1,980 ms
4,368 KB
testcase_10 AC 1,981 ms
4,372 KB
testcase_11 AC 1,981 ms
4,368 KB
testcase_12 AC 1,981 ms
4,368 KB
testcase_13 AC 1,981 ms
4,372 KB
testcase_14 AC 1,981 ms
4,368 KB
testcase_15 AC 1,981 ms
4,368 KB
testcase_16 AC 1,982 ms
4,372 KB
testcase_17 AC 1,982 ms
4,372 KB
testcase_18 AC 1,981 ms
4,368 KB
testcase_19 AC 1,982 ms
4,368 KB
testcase_20 AC 1,982 ms
4,368 KB
testcase_21 AC 1,981 ms
4,372 KB
testcase_22 AC 1,981 ms
4,372 KB
testcase_23 AC 1,981 ms
4,372 KB
testcase_24 AC 1,981 ms
4,372 KB
testcase_25 AC 1,981 ms
4,372 KB
testcase_26 AC 1,982 ms
4,372 KB
testcase_27 AC 1,980 ms
4,372 KB
testcase_28 AC 1,981 ms
4,368 KB
testcase_29 AC 1,982 ms
4,368 KB
testcase_30 AC 1,982 ms
4,368 KB
testcase_31 AC 1,982 ms
4,372 KB
testcase_32 AC 1,981 ms
4,368 KB
testcase_33 AC 1,982 ms
4,368 KB
testcase_34 AC 1,981 ms
4,368 KB
testcase_35 AC 1,981 ms
4,368 KB
testcase_36 AC 1,981 ms
4,368 KB
testcase_37 AC 1,982 ms
4,372 KB
testcase_38 AC 1,981 ms
4,368 KB
testcase_39 AC 1,982 ms
4,368 KB
testcase_40 AC 1,982 ms
4,372 KB
testcase_41 AC 1,981 ms
4,368 KB
testcase_42 AC 1,981 ms
4,372 KB
testcase_43 AC 1,981 ms
4,368 KB
testcase_44 AC 1,981 ms
4,368 KB
testcase_45 AC 1,982 ms
4,368 KB
testcase_46 AC 1,982 ms
4,372 KB
testcase_47 AC 1,982 ms
4,368 KB
testcase_48 AC 1,981 ms
4,372 KB
testcase_49 AC 1,982 ms
4,368 KB
testcase_50 AC 1,980 ms
4,368 KB
testcase_51 AC 1,982 ms
4,368 KB
testcase_52 AC 1,981 ms
4,376 KB
testcase_53 AC 1,982 ms
4,368 KB
testcase_54 AC 1,982 ms
4,372 KB
testcase_55 AC 1,981 ms
4,368 KB
testcase_56 AC 1,981 ms
4,372 KB
testcase_57 AC 1,981 ms
4,372 KB
testcase_58 AC 1,982 ms
4,368 KB
testcase_59 AC 1,981 ms
4,372 KB
testcase_60 AC 1,981 ms
4,368 KB
testcase_61 AC 1,980 ms
4,368 KB
testcase_62 AC 1,982 ms
4,368 KB
testcase_63 AC 1,982 ms
4,368 KB
testcase_64 AC 1,982 ms
4,372 KB
testcase_65 AC 1,981 ms
4,368 KB
testcase_66 AC 1,982 ms
4,372 KB
testcase_67 AC 1,981 ms
4,372 KB
testcase_68 AC 1,981 ms
4,372 KB
testcase_69 AC 1,981 ms
4,372 KB
testcase_70 AC 1,981 ms
4,372 KB
testcase_71 AC 1,981 ms
4,368 KB
testcase_72 AC 1,981 ms
4,368 KB
testcase_73 AC 1,981 ms
4,368 KB
testcase_74 AC 1,981 ms
4,368 KB
testcase_75 AC 1,981 ms
4,368 KB
testcase_76 AC 1,981 ms
4,368 KB
testcase_77 AC 1,982 ms
4,368 KB
testcase_78 AC 1,982 ms
4,372 KB
testcase_79 AC 1,981 ms
4,372 KB
testcase_80 AC 1,982 ms
4,368 KB
testcase_81 AC 1,982 ms
4,368 KB
testcase_82 AC 1,981 ms
4,368 KB
testcase_83 AC 1,981 ms
4,368 KB
testcase_84 AC 1,982 ms
4,372 KB
testcase_85 AC 1,981 ms
4,368 KB
testcase_86 AC 1,981 ms
4,368 KB
testcase_87 AC 1,982 ms
4,368 KB
testcase_88 AC 1,981 ms
4,368 KB
testcase_89 AC 1,981 ms
4,376 KB
testcase_90 AC 1,982 ms
4,368 KB
testcase_91 AC 1,980 ms
4,372 KB
testcase_92 AC 1,981 ms
4,368 KB
testcase_93 AC 1,981 ms
4,368 KB
testcase_94 AC 1,982 ms
4,372 KB
testcase_95 AC 1,982 ms
4,368 KB
testcase_96 AC 1,980 ms
4,372 KB
testcase_97 AC 1,981 ms
4,368 KB
testcase_98 AC 1,981 ms
4,368 KB
testcase_99 AC 1,981 ms
4,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![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 N: usize = 36; // 操作回数
const NUM_DICE: usize = 6; // 操作1回当りのダイスの数
const BOARD_SIZE: usize = 6; // ダイスを配置するセルのサイズ
const TL: f64 = 1.98; // 全体の制限時間
const T0: f64 = 15.0; // 焼きなまし初期温度
const T1: f64 = 1.0; // 焼きなまし終温度
const MULTI_START: f64 = 5.; // 多点スタートする回数

/// proconioみたいなやつ
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());
    }
}

/// 疑似乱数xoshiro256
/// yukicoderでRustのrand crateが使えないため
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)]
pub struct Input {
    dice: Vec<Vec<usize>>, // dice[i][j] := i回目のダイスjの出目
}
impl Input {
    fn new() -> Self {
        input! {
            dice: [[usize; NUM_DICE]; N],
        }
        Self { dice }
    }
}

/// 6x6のセルの状態を保持するための構造体
#[derive(Clone)]
struct State {
    cell: Vec<usize>, // cell[i * BOARD_SIZE + j] := i行j列目に置かれたのが何操作目の出目か
}
impl State {
    // 構造体とメンバ変数を初期化する
    fn new() -> Self {
        // どこに何を置くかすべて決まらないとスコアが得られないので，とりあえず置く
        let mut cell = vec![];
        for i in 0..BOARD_SIZE {
            for j in 0..BOARD_SIZE {
                cell.push(i * BOARD_SIZE + j);
            }
        }
        // 入力例1の出力を使って，スコア計算の妥当性を確認する用
        // let mut cell = vec![0; BOARD_SIZE * BOARD_SIZE];
        // for i in 0..N {
        //     input! {
        //         xi: Usize1,
        //         yi: Usize1,
        //     }
        //     cell[xi * BOARD_SIZE + yi] = i;
        // }
        Self {cell}
    }
    // スコアを計算する
    fn calc_score(&mut self, input: &Input) -> 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 = &input.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 = &input.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
    }

    // 回答を出力する
    fn print(&self) {
        // cell[i * BOARD_SIZE + j] = 何番目の操作か なのだから，cellをargsortして出力すれば良い
        let mut index = (0..N).collect::<Vec<_>>();
        // 昇順ソート
        index.sort_by(|&i, &j| self.cell[i].cmp(&self.cell[j]));
        // 1-indexに直しつつ出力
        for &i in &index {
            println!("{} {}", i / BOARD_SIZE + 1, i % BOARD_SIZE + 1);
        }
    }
}

fn main() {
    get_time();
    let input = Input::new();
    let mut crt_state = State::new();
    let mut crt_score = crt_state.calc_score(&input);
    let mut best_state = crt_state.clone();
    let mut best_score = crt_score;
    let mut rng = Xoshiro256::new(8192);

    // セルを弄ってスコアが上がるなら採用するという山登りを繰り返す
    let mut total_iter = 0;
    let mut accepted_count = 0;
    let mut update_best_count = 0;
    while get_time() < TL {
        total_iter += 1;
        let t = get_time() / TL;
        let T = T0.powf(1.0 - t) * T1.powf(t);
        // 0~35番のどのセルを交換するか決める
        let cell_1 = rng.gen_usize(0, N - 1);
        let cell_2 = rng.gen_usize(cell_1 + 1, N);
        crt_state.cell.swap(cell_1, cell_2);
        let next_score = crt_state.calc_score(&input);

        // スコアがベストを更新するなら，その構造体を保存する
        if best_score < next_score {
            best_state = crt_state.clone();
            best_score = next_score;
            update_best_count += 1;
        }

        if crt_score <= next_score || rng.gen_bool(f64::exp(-(crt_score - next_score) as f64 / T)) {
            // 前回よりいいか，焼きなましが許容するなら採用する
            crt_score = next_score;
            accepted_count += 1;
        } else {
            // そうでないならリバートする
            crt_state.cell.swap(cell_1, cell_2);
        }

    }

    best_state.print();

    eprintln!("score: {}", best_score);
    eprintln!("total iter: {}", total_iter);
    eprintln!("accepted: {}", accepted_count);
    eprintln!("update best: {}", update_best_count);
    eprintln!("time: {}", get_time());
}
0