#1108088 (Rust) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: r3yohei
• 提出日時: 2025-07-26 16:46:39
• 言語: Rust (1.83.0 + proconio)
• 結果: TLE
• 実行時間: -
• コード長: 12,339 bytes
• コンパイル時間: 13,819 ms
• コンパイル使用メモリ: 398,228 KB
• 実行使用メモリ: 7,716 KB
• スコア: 5,052,508,332
• 最終ジャッジ日時: 2025-07-26 16:48:34
• 合計ジャッジ時間: 114,199 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

ファイルパターン	結果
other	AC * 49 TLE * 1

コンパイルメッセージ

warning: unexpected `cfg` condition value: `local`
  --> src/main.rs:32:15
   |
32 |         #[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:36:19
   |
36 |         #[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

ソースコード

#![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.9;
const N: usize = 10;
const NN: usize = N * N;
const T: usize = 1000;
const TH: i64 = 1000000;

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
        }
    }
}

/// ベクタのargsort
fn argsort<T: Ord>(v: &[T]) -> Vec<usize> {
    let mut idx = (0..v.len()).collect::<Vec<_>>();
    idx.sort_by(|&i, &j| v[j].cmp(&v[i]));
    idx
}

/// 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>,
    turn: usize,
    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, turn: 0, score }
    }
    fn search(&self, mut rng: &mut Xoshiro256) -> (Vec<usize>, Vec<usize>, i64, usize) {
        // 改善量が一番多いsのコピー元と、書き込み先のリストを探索する
        let mut best_c_pos = vec![];
        let mut best_w_pos = vec![];
        let mut best_score_diff = 0;
        let mut best_turn = 0;

        // sのコピー元を全探索
        for cij_1 in 0..NN {
            for cij_2 in 0..NN {
                // 2回まで連続コピーありにする
                let next_s = if cij_1 == cij_2 {
                    self.s ^ self.A[cij_1]
                } else {
                    // !! cij_1 -> cij_2の順に移動することに注意 !!
                    (self.s ^ self.A[cij_1]) ^ self.A[cij_2]
                };
                let mut score_diff = vec![];
                let mut w_pos = vec![];
                // 書き込み先のリストを全探索
                for wij in 0..NN {
                    // if self.A[wij] < (self.A[wij] ^ next_s) {
                    if (self.A[wij] ^ next_s) > TH && rng.gen_bool(0.5) {
                        // 書き込みで改善するならスコアに計上して書き込み先リストに追加
                        score_diff.push((self.A[wij] ^ next_s) - self.A[wij]);
                        w_pos.push(wij);
                    }
                }

                // スコアの改善幅の大きい上位10箇所を選ぶ
                let mut sorted_idx = argsort(&score_diff);
                sorted_idx.truncate(12);
                let score_diff_sum = sorted_idx.iter().map(|&i| score_diff[i]).sum::<i64>();

                // この時点で見込みが無ければスキップ
                if best_score_diff >= score_diff_sum {
                    continue;
                }

                // w_posを上位10箇所に絞る
                w_pos = sorted_idx.iter().map(|&i| w_pos[i]).collect();

                // sのコピー元への移動手数を計算する
                let (c_pos, dist_c_pos) = if cij_1 == cij_2 {
                    (vec![cij_1], (self.pos / N).abs_diff(cij_1 / N)
                        + (self.pos % N).abs_diff(cij_1 % N))
                } else {
                    (vec![cij_1, cij_2], 
                        (self.pos / N).abs_diff(cij_1 / N)
                        + (self.pos % N).abs_diff(cij_1 % N)
                        + (cij_1 / N).abs_diff(cij_2 / N)
                        + (cij_1 % N).abs_diff(cij_2 % N))
                };
                // tspで最短経路を計算
                let (w_tsp_idx, w_tsp_turn) = tsp(cij_2, &w_pos);

                // 現在のターン + 現在地からコピー元へ行くターン + tspのターンがTを超えてはならない
                if self.turn
                    + dist_c_pos + c_pos.len() // C操作のターン
                    + w_tsp_turn + w_pos.len() // W操作のターン
                    > T {
                    // Tターンを超える場合はスキップ
                    continue;
                }

                // tspの結果をc_pos, w_posに反映
                w_pos = w_tsp_idx.iter().map(|&i| w_pos[i]).collect();

                // ベストの更新
                if best_score_diff.chmax(score_diff_sum) {
                    best_turn = self.turn
                        + dist_c_pos + c_pos.len()
                        + w_tsp_turn + w_pos.len();
                    best_c_pos = c_pos;
                    best_w_pos = w_pos;
                }
            }
        }

        (best_c_pos, best_w_pos, best_score_diff, best_turn)
    }
    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 tsp(crt_pos: usize, dst_pos: &Vec<usize>) -> (Vec<usize>, usize) {
    let mut dp = vec![vec![usize::MAX / 2; dst_pos.len()]; 1 << dst_pos.len()];
    let mut from = vec![vec![(!0, !0); dst_pos.len()]; 1 << dst_pos.len()];

    for i in 0..dst_pos.len() {
        dp[1 << i][i] = (crt_pos / N).abs_diff(dst_pos[i] / N)
            + (crt_pos % N).abs_diff(dst_pos[i] % N);
    }

    for flag in 1..1 << dst_pos.len() {
        for i in 0..dst_pos.len() {
            if flag & 1 << i == 0 {
                continue;
            }

            for j in 0..dst_pos.len() {
                if flag & 1 << j != 0 {
                    continue;
                }

                let new_flag = flag | 1 << j;
                let new_dist = dp[flag][i]
                    + (dst_pos[i] / N).abs_diff(dst_pos[j] / N)
                    + (dst_pos[i] % N).abs_diff(dst_pos[j] % N);

                if dp[new_flag][j].chmin(new_dist) {
                    from[new_flag][j] = (flag, i);
                }
            }
        }
    }

    let mut best_i = !0;
    let mut best_dist = usize::MAX;

    for i in 0.. dst_pos.len() {
        if best_dist.chmin(dp[(1 << dst_pos.len()) - 1][i]) {
            best_i = i;
        }
    }

    let mut route = vec![];
    let mut flag = (1 << dst_pos.len()) - 1;
    let mut i = best_i;

    while flag != !0 {
        route.push(i);
        let (next_flag, next_i) = from[flag][i];
        flag = next_flag;
        i = next_i;
    }

    route.reverse();

    (route, best_dist)
}

fn solve() {
    let mut rng = Xoshiro256::new(8192);
    let input = Input::new();
    
    let mut best_score = 0;
    let mut best_op = vec![];
    
    while get_time() < TL {
        let mut state = State::new(&input);
        let mut op = vec![];
        while op.len() < T && get_time() < TL {
            let (c_pos, w_pos, score_diff, turn) = state.search(&mut rng);
            if c_pos.is_empty() || w_pos.is_empty() {
                // 改善できるsのコピー元がない場合は終了
                // eprintln!("cannot improve anymore");
                break;
            }
            let mut crt_pos = state.pos;
            let mut next_op = vec![];
            for &c_pos in &c_pos {
                // sのコピー元へ移動
                let tmp_op = state.calc_move_operation(crt_pos, c_pos);
                next_op.extend(tmp_op);
                next_op.push('C');
                crt_pos = c_pos;
            }

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

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

            op.extend(next_op);
        }

        if best_score.chmax(state.score) {
            best_op = op.clone();
            eprintln!("update best score: {}", best_score);
        }
    }


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

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

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