結果

問題 No.5022 XOR Printer
ユーザー r3yohei
提出日時 2025-07-26 14:37:41
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 8,111 bytes
コンパイル時間 13,194 ms
コンパイル使用メモリ 398,080 KB
実行使用メモリ 7,716 KB
スコア 4,874,900,824
最終ジャッジ日時 2025-07-26 14:37:58
合計ジャッジ時間 16,201 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
  --> src/main.rs:31:15
   |
31 |         #[cfg(feature = "local")]
   |               ^^^^^^^^^^^^^^^^^ help: remove the condition
   |
   = note: no expected values for `feature`
   = help: consider adding `local` as a feature in `Cargo.toml`
   = note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
   = note: `#[warn(unexpected_cfgs)]` on by default

warning: unexpected `cfg` condition value: `local`
  --> src/main.rs:35:19
   |
35 |         #[cfg(not(feature = "local"))]
   |                   ^^^^^^^^^^^^^^^^^ help: remove the condition
   |
   = note: no expected values for `feature`
   = help: consider adding `local` as a feature in `Cargo.toml`
   = note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration

ソースコード

diff # 

#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(unused_mut)]
#![allow(non_upper_case_globals)]
use proconio::{marker::*, source::line::LineSource, *};
use std::io::*;
use std::{cmp::*, vec};
use std::{collections::*, fmt::format};

const INF: i64 = 1 << 60;
const SEED: u128 = 8_192;
const DIJ: [(usize, usize); 4] = [(0, !0), (0, 1), (!0, 0), (1, 0)];
const DIR: [char; 4] = ['L', 'R', 'U', 'D'];
const TL: f64 = 1.989;
const N: usize = 10;
const NN: usize = N * N;
const T: usize = 1000;

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;
        }
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.5
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}

pub trait ChangeMinMax {
    fn chmin(&mut self, x: Self) -> bool;
    fn chmax(&mut self, x: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, x: Self) -> bool {
        *self > x && {
            *self = x;
            true
        }
    }
    fn chmax(&mut self, x: Self) -> bool {
        *self < x && {
            *self = x;
            true
        }
    }
}

/// seed値を4つの初期状態値に分割するためのsplit mix 64
struct SplitMix64 {
    s: u64,
}
impl SplitMix64 {
    fn new(seed: u64) -> Self {
        Self { s: seed }
    }
    fn next_u64(&mut self) -> u64 {
        self.s = self.s.wrapping_add(0x9e3779b97f4a7c15);
        let mut z = self.s;
        z = (z ^ z >> 30).wrapping_mul(0xbf58476d1ce4e5b9);
        z = (z ^ z >> 27).wrapping_mul(0x94d049bb133111eb);
        z ^ z >> 31
    }
}
/// Xoshiro256による乱数生成器
struct Xoshiro256 {
    s: [u64; 4],
}
impl Xoshiro256 {
    fn new(seed: u64) -> Self {
        let mut split_mix_64 = SplitMix64::new(seed);
        let mut s = [0; 4];
        for si in &mut s {
            *si = split_mix_64.next_u64();
        }
        Self { s }
    }
    fn next_u64(&mut self) -> u64 {
        let result = (self.s[1].wrapping_mul(5)).rotate_left(7).wrapping_mul(9);
        let t = self.s[1] << 17;
        self.s[2] ^= self.s[0];
        self.s[3] ^= self.s[1];
        self.s[1] ^= self.s[2];
        self.s[0] ^= self.s[3];
        self.s[2] ^= t;
        self.s[3] = self.s[3].rotate_left(45);
        result
    }
    fn gen_usize(&mut self, lower: usize, upper: usize) -> usize {
        assert!(lower < upper);
        let count = upper - lower;
        (self.next_u64() % count as u64) as usize + lower
    }
    fn gen_i64(&mut self, lower: i64, upper: i64) -> i64 {
        assert!(lower < upper);
        let count = upper - lower;
        (self.next_u64() % count as u64) as i64 + lower
    }
    fn gen_f64(&mut self) -> f64 {
        const UPPER_MASK: u64 = 0x3ff0000000000000;
        const LOWER_MASK: u64 = 0xfffffffffffff;
        let result = UPPER_MASK | (self.next_u64() & LOWER_MASK);
        let result: f64 = unsafe { std::mem::transmute(result) };
        result - 1.0
    }
    fn gen_bool(&mut self, prob: f64) -> bool {
        self.gen_f64() < prob
    }
    fn fisher_yates_shuffle<T>(&mut self, items: &mut [T]) {
        for i in (1..items.len()).rev() {
            let j = (self.next_u64() as usize) % (i + 1);
            items.swap(j, i);
        }
    }
}

#[derive(Clone, Debug)]
struct Input {
    A: Vec<Vec<i64>>,
}
impl Input {
    fn new() -> Self {
        input! {
            _N: usize,
            _T: usize,
            A: [[i64; N]; N],
        }

        Self { A }
    }
}

#[derive(Clone, Debug)]
struct State {
    pos: usize,
    s: i64,
    A: Vec<i64>,
    score: i64,
}
impl State {
    fn new(input: &Input) -> Self {
        let mut A = vec![0; NN];
        let mut score = 0;
        for i in 0..N {
            for j in 0..N {
                A[i * N + j] = input.A[i][j];
                score += input.A[i][j];
            }
        }
        Self { pos: 0, s: 0, A, score }
    }
    fn search(&self, forbidden_c_pos: &HashSet<usize>, rng: &mut Xoshiro256) -> (usize, Vec<usize>, i64) {
        // 改善量が一番多いsのコピー元と、書き込み先のリストを探索する
        let mut best_score_diff = 0;
        let mut best_c_pos = !0;
        let mut best_w_pos = vec![];
        // sのコピー元を全探索
        for ij in 0..NN {
            if forbidden_c_pos.contains(&ij) {
                continue; // 禁止されているコピー元はスキップ
            }
            let next_s = self.s ^ self.A[ij];
            let mut score_diff = 0;
            let mut w_pos = vec![];
            // 書き込み先のリストを全探索
            for ij2 in 0..NN {
                if ij == ij2 {
                    continue;
                }
                if self.A[ij2] < (self.A[ij2] ^ next_s) && rng.gen_bool(0.6) {
                    // 書き込みで改善するならスコアに計上して書き込み先リストに追加
                    // 最初はほとんど改善しちゃうので確率的に選ぶ
                    score_diff += (self.A[ij2] ^ next_s) - self.A[ij2];
                    w_pos.push(ij2);
                }
            }
            // ベストの更新
            if best_score_diff.chmax(score_diff) {
                best_c_pos = ij;
                best_w_pos = w_pos;
            }
        }
        // TODO: Tターン以内に間に合うか調べる機構を入れる

        (best_c_pos, best_w_pos, best_score_diff)
    }
    fn calc_move_operation(&self, crt_pos: usize, next_pos: usize) -> Vec<char> {
        // posからnext_posに移動する操作を計算
        let (crt_x, crt_y) = (crt_pos / N, crt_pos % N);
        let (next_x, next_y) = (next_pos / N, next_pos % N);
        let mut move_op = vec![];
        if crt_x < next_x {
            for _ in 0..(next_x - crt_x) {
                move_op.push('D');
            }
        } else if crt_x > next_x {
            for _ in 0..(crt_x - next_x) {
                move_op.push('U');
            }
        }
        if crt_y < next_y {
            for _ in 0..(next_y - crt_y) {
                move_op.push('R');
            }
        } else if crt_y > next_y {
            for _ in 0..(crt_y - next_y) {
                move_op.push('L');
            }
        }

        move_op
    }
}

fn solve() {
    let mut rng = Xoshiro256::new(8192);
    let input = Input::new();
    let mut state = State::new(&input);
    let mut move_op = vec![];
    let mut forbidden_c_pos = HashSet::new();
    while move_op.len() < T && get_time() < TL {
        let (c_pos, w_pos, score_diff) = state.search(&forbidden_c_pos, &mut rng);
        if c_pos == !0 || w_pos.is_empty() {
            // 改善できるsのコピー元がない場合は終了
            break;
        }
        let mut crt_pos = state.pos;
        let mut next_move_op = state.calc_move_operation(crt_pos, c_pos);
        next_move_op.push('C');
        crt_pos = c_pos;

        for &next_pos in &w_pos {
            let tmp_move_op = state.calc_move_operation(crt_pos, next_pos);
            next_move_op.extend(tmp_move_op);
            next_move_op.push('W');
            crt_pos = next_pos;
        }

        if move_op.len() + next_move_op.len() > T {
            // Tターンを超える場合はスキップ
            forbidden_c_pos.insert(c_pos);
            continue;
        }

        // 書き込み後の状態を更新
        state.s ^= state.A[c_pos];
        for &next_pos in &w_pos {
            state.A[next_pos] ^= state.s;
        }
        state.pos = crt_pos;
        state.score += score_diff;

        move_op.extend(next_move_op);
    }


    for &op in &move_op {
        println!("{}", op);
    }

    eprintln!("time: {:.3} sec", get_time());
    eprintln!("score: {}", state.score);
}

fn main() {
    get_time();
    solve();
}
0