#1141673 (Rust) No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: tomerun
• 提出日時: 2025-12-25 02:15:53
• 言語: Rust (1.83.0 + proconio)
• 結果: TLE
• 実行時間: -
• コード長: 13,695 bytes
• コンパイル時間: 14,652 ms
• コンパイル使用メモリ: 397,632 KB
• 実行使用メモリ: 34,032 KB
• スコア: 0
• 最終ジャッジ日時: 2025-12-25 02:18:29
• 合計ジャッジ時間: 25,525 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	TLE * 1 -- * 99

ソースコード

#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(non_snake_case)]
use std::cmp::Ordering;
use std::env;
use std::io::{self, BufRead, BufReader, Read, Stdin};
use std::iter;
use std::mem;
use std::str::FromStr;
use std::string::String;
use std::time;

const LOCAL: bool = false;
const TIMELIMIT: u64 = 4900;
const INF: usize = 1 << 28;
const N: usize = 30;
const L: usize = 5;

#[derive(Debug)]
pub struct Scanner<R> {
    reader: BufReader<R>,
}

fn scanner() -> Scanner<Stdin> {
    Scanner::new(io::stdin())
}

impl<R: io::Read> Scanner<R> {
    pub fn new(read: R) -> Scanner<R> {
        Scanner {
            reader: BufReader::new(read),
        }
    }

    pub fn next_str(&mut self) -> Option<String> {
        let mut buf = [0; 1];
        let size = self.reader.read(&mut buf).unwrap();
        if size == 0 {
            None
        } else {
            self.skip_whitespace(&mut buf)?;
            let mut v = vec![buf[0]];
            loop {
                let size = self.reader.read(&mut buf).unwrap();
                if size == 0 || buf[0].is_ascii_whitespace() {
                    break;
                }
                v.push(buf[0]);
            }
            Some(String::from_utf8(v).unwrap())
        }
    }

    pub fn next_line(&mut self) -> String {
        let mut line = String::new();
        self.reader.read_line(&mut line).unwrap();
        if let Some(s) = line.strip_suffix("\n") {
            s.to_string()
        } else {
            line
        }
    }

    pub fn vec<S: FromStr>(&mut self, size: i32) -> Vec<S> {
        let mut v: Vec<S> = vec![];
        for _ in 0..size {
            let token = self.next_str().unwrap();
            v.push(S::from_str(&token).ok().unwrap());
        }
        v
    }

    pub fn next_as<S: FromStr>(&mut self) -> Option<S> {
        let s = self.next_str()?;
        S::from_str(&s).ok()
    }

    pub fn str(&mut self) -> String {
        self.next_str().unwrap()
    }

    pub fn i32(&mut self) -> i32 {
        self.next_as::<i32>().unwrap()
    }

    pub fn u32(&mut self) -> u32 {
        self.next_as::<u32>().unwrap()
    }

    pub fn i64(&mut self) -> i64 {
        self.next_as::<i64>().unwrap()
    }

    pub fn u64(&mut self) -> u64 {
        self.next_as::<u64>().unwrap()
    }

    pub fn usize(&mut self) -> usize {
        self.next_as::<usize>().unwrap()
    }

    fn skip_whitespace(&mut self, mut buf: &mut [u8]) -> Option<u8> {
        loop {
            if !buf[0].is_ascii_whitespace() {
                return Some(buf[0]);
            }
            let size = self.reader.read(&mut buf).unwrap();
            if size == 0 {
                return None;
            }
        }
    }
}

struct XorShift32 {
    state: u32,
}

impl XorShift32 {
    fn from_seed(seed: u32) -> Self {
        let initial_state = if seed == 0 { 1 } else { seed };
        XorShift32 { state: initial_state }
    }

    fn next_u32(&mut self) -> u32 {
        let mut x = self.state;
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        self.state = x;
        x
    }

    fn next_u64(&mut self) -> u64 {
        ((self.next_u32() as u64) << 32) | (self.next_u32() as u64)
    }

    fn next_f64(&mut self) -> f64 {
        self.next_u32() as f64 / (u32::MAX as f64 + 1.0)
    }
}

#[derive(Debug)]
struct Timer {
    start_time: time::Instant,
    limit: time::Instant,
    before_time: Option<time::Instant>,
    worst_time: time::Duration,
}

impl Timer {
    fn new(tl: u64) -> Timer {
        let start_time = time::Instant::now();
        Timer {
            start_time,
            limit: start_time + time::Duration::from_millis(tl),
            before_time: None,
            worst_time: time::Duration::from_millis(0),
        }
    }

    fn elapsed(&self) -> u64 {
        self.start_time.elapsed().as_millis() as u64
    }

    fn checkpoint(&mut self) {
        if let Some(before_time) = self.before_time {
            let elapsed = before_time.elapsed();
            self.worst_time = self.worst_time.max(elapsed);
        }
        self.before_time = Some(time::Instant::now());
    }

    fn tl(&self) -> u64 {
        (self.limit - self.start_time).as_millis() as u64
    }

    fn tl_exceeded(&self) -> bool {
        self.limit < time::Instant::now()
    }

    fn should_stop(&self) -> bool {
        self.limit < time::Instant::now() + self.worst_time
    }

    fn should_stop_with_margin(&self, margin: u64) -> bool {
        self.limit < time::Instant::now() + self.worst_time + time::Duration::from_millis(margin)
    }
}

fn count(q0: &[usize; 5], q1: &[usize; 5]) -> (usize, usize) {
    let mut hit = 0;
    let mut v0 = 0usize;
    let mut v1 = 0usize;
    for i in 0..5 {
        if q0[i] == q1[i] {
            hit += 1;
        }
        v0 |= 1 << q0[i];
        v1 |= 1 << q1[i];
    }
    let blow = (v0 & v1).count_ones() as usize - hit;
    (hit, blow)
}

fn pack(q: &[usize; 5]) -> usize {
    let mut res = 0usize;
    for i in 0..5 {
        res = res * 10 + q[i];
    }
    res
}

#[derive(Debug, Clone)]
struct History {
    q: [usize; 5],
    result: [[usize; 6]; 6],
}

impl History {
    fn new(q: &[usize; 5], hb: &[(usize, usize); N]) -> History {
        let mut result = [[0usize; 6]; 6];
        for i in 0..N {
            let (h, b) = hb[i];
            result[h][b] += 1;
        }
        History { q: *q, result }
    }
}

struct Solver {
    scanner: Scanner<Stdin>,
    timer: Timer,
    rng: XorShift32,
    all_q: Vec<[usize; 5]>,
    truth: [[usize; 5]; N],
    done: [bool; N],
}

impl Solver {
    fn new() -> Solver {
        let tl = env::var("TL").map_or(TIMELIMIT, |v| v.parse().unwrap());
        let timer = Timer::new(tl);
        let seed = env::var("SEED").map_or(2, |v| v.parse().unwrap());
        let mut rng = XorShift32::from_seed(seed);
        let mut all_q = vec![];
        for i0 in 0..=9 {
            for i1 in 0..=9 {
                if i1 == i0 {
                    continue;
                }
                for i2 in 0..=9 {
                    if i2 == i1 || i2 == i0 {
                        continue;
                    }
                    for i3 in 0..=9 {
                        if i3 == i2 || i3 == i1 || i3 == i0 {
                            continue;
                        }
                        for i4 in 0..=9 {
                            if i4 == i3 || i4 == i2 || i4 == i1 || i4 == i0 {
                                continue;
                            }
                            all_q.push([i0, i1, i2, i3, i4]);
                        }
                    }
                }
            }
        }
        let scanner = scanner();
        let mut truth = [[0usize; 5]; N];
        if LOCAL {
            for i in 0..N {
                truth[i] = all_q[rng.next_u32() as usize % all_q.len()];
            }
            eprintln!("truth:{:?}", truth);
        }
        Solver {
            scanner,
            timer,
            rng,
            all_q,
            truth,
            done: [false; N],
        }
    }

    fn solve(&mut self) {
        let mut answer = vec![];
        let mut history = vec![];
        let initial_qis = [0, 4000, 8000, 12000, 16000, 20000, 24000, 28000];
        let mut used_queries = vec![];
        for qi in initial_qis {
            let q = self.all_q[qi];
            let mut hb = self.query(&q);
            used_queries.push(pack(&q));
            for ai in 0..answer.len() {
                hb[N - 1 - ai] = count(&answer[ai], &q);
            }
            if hb[N - 1 - answer.len()] == (5, 0) {
                answer.push(q);
            }
            history.push(History::new(&q, &hb));
        }
        let mut hypo = [[0; 5]; N];
        for i in 0..N - answer.len() {
            let mut qi = self.rng.next_u32() as usize % self.all_q.len();
            while hypo.contains(&self.all_q[qi]) {
                qi = self.rng.next_u32() as usize % self.all_q.len();
            }
            hypo[i] = self.all_q[qi];
        }
        let mut turn = used_queries.len();
        while answer.len() < N {
            turn += 1;
            self.update_hypothesis(&history, &mut hypo, answer.len());

            let mut pos = INF;
            for i in 0..N - answer.len() {
                if !used_queries.contains(&pack(&hypo[i])) {
                    pos = i;
                    break;
                }
            }
            if pos == INF {
                pos = 0;
                let mut qi = self.rng.next_u32() as usize % self.all_q.len();
                let mut q = self.all_q[qi];
                while hypo.contains(&q) || used_queries.contains(&pack(&q)) {
                    qi = self.rng.next_u32() as usize % self.all_q.len();
                    q = self.all_q[qi];
                }
                hypo[pos] = q;
            }
            let q = hypo[pos];
            used_queries.push(pack(&q));
            let mut hb = self.query(&q);
            for ai in 0..answer.len() {
                assert!(hb[N - 1 - ai].0 == 5);
                hb[N - 1 - ai] = count(&answer[ai], &q);
            }
            history.push(History::new(&q, &hb));
            if hb[N - 1 - answer.len()] == (5, 0) {
                hypo.swap(pos, N - 1 - answer.len());
                answer.push(q);
            }
        }
        eprintln!("score:{:?}", turn);
    }

    fn update_hypothesis(&mut self, history: &Vec<History>, hypo: &mut [[usize; 5]; N], answer_cnt: usize) {
        let mut counts = vec![[[0usize; 6]; 6]; history.len()];
        let mut penalty = 0i32;
        for i in 0..history.len() {
            for j in 0..N {
                let (h, b) = count(&history[i].q, &hypo[j]);
                counts[i][h][b] += 1;
            }
            for h in 0..6 {
                for b in 0..6 {
                    let c = history[i].result[h][b];
                    penalty += counts[i][h][b].abs_diff(c) as i32;
                }
            }
        }
        let initial_penalty = penalty;
        for _ in 0..50000 {
            let ch_i = self.rng.next_u32() as usize % (N - answer_cnt);
            let old_q = hypo[ch_i];
            let mut new_q;
            loop {
                let ch_type = self.rng.next_u32() & 3;
                if ch_type == 0 {
                    let p0 = self.rng.next_u32() as usize % 5;
                    let mut p1 = self.rng.next_u32() as usize % 4;
                    if p1 >= p0 {
                        p1 += 1;
                    }
                    new_q = old_q;
                    new_q.swap(p0, p1);
                } else if ch_type == 1 {
                    let qi = self.rng.next_u32() as usize % self.all_q.len();
                    new_q = self.all_q[qi];
                } else {
                    let p0 = self.rng.next_u32() as usize % 5;
                    new_q = old_q;
                    let mut digit = self.rng.next_u32() as usize % 10;
                    while new_q.contains(&digit) {
                        digit = self.rng.next_u32() as usize % 10;
                    }
                    new_q[p0] = digit;
                }
                if !hypo.contains(&new_q) {
                    break;
                }
            }
            let mut diff = 0;
            for i in 0..history.len() {
                let (h_old, b_old) = count(&history[i].q, &old_q);
                let (h_new, b_new) = count(&history[i].q, &new_q);
                if h_old == h_new && b_old == b_new {
                    continue;
                }
                if counts[i][h_old][b_old] > history[i].result[h_old][b_old] {
                    diff -= 1;
                } else {
                    diff += 1;
                }
                if counts[i][h_new][b_new] >= history[i].result[h_new][b_new] {
                    diff += 1;
                } else {
                    diff -= 1;
                }
            }
            if self.accept(diff) {
                hypo[ch_i] = new_q;
                penalty += diff;
                for i in 0..history.len() {
                    let (h_old, b_old) = count(&history[i].q, &old_q);
                    let (h_new, b_new) = count(&history[i].q, &new_q);
                    counts[i][h_old][b_old] -= 1;
                    counts[i][h_new][b_new] += 1;
                }
                if penalty == 0 {
                    break;
                }
            }
        }
        eprintln!("penalty:{:?}->{:?}", initial_penalty, penalty);
        // eprintln!("hypothesis{:?}", hypo);
    }

    fn accept(&mut self, diff: i32) -> bool {
        if diff <= 0 {
            return true;
        }
        false
        // self.rng.next_f64() < (-diff as f64 * 2.0).exp()
    }

    fn query(&mut self, q: &[usize; 5]) -> [(usize, usize); N] {
        let mut hit_blow = [(0, 0); N];
        if LOCAL {
            for i in 0..N {
                if self.done[i] {
                    hit_blow[i] = (5, 0);
                } else {
                    hit_blow[i] = count(&self.truth[i], q);
                    if hit_blow[i] == (5, 0) {
                        self.done[i] = true;
                    }
                }
            }
            hit_blow.sort();
            eprintln!("q:{:?}", q);
            eprintln!("res:{:?}", hit_blow);
        } else {
            println!("{}{}{}{}{}", q[0], q[1], q[2], q[3], q[4]);
            for i in 0..N {
                let hit = self.scanner.usize();
                let blow = self.scanner.usize();
                hit_blow[i] = (hit, blow);
            }
        }
        hit_blow
    }
}

fn main() {
    let mut solver = Solver::new();
    solver.solve()
}