結果

問題 No.5005 3-SAT
ユーザー Tekyla
提出日時 2025-12-29 16:20:19
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 1,902 ms / 2,000 ms
コード長 4,493 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,386 ms
コンパイル使用メモリ 400,268 KB
実行使用メモリ 7,852 KB
スコア 20,802
最終ジャッジ日時 2025-12-29 16:23:56
合計ジャッジ時間 208,996 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
  --> src/main.rs:21:15
   |
21 |         #[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:25:19
   |
25 |         #[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

warning: field `state` is never read
  --> src/main.rs:35:5
   |
34 | struct XorShift32 {
   |        ---------- field in this struct
35 |     state: u32,
   |     ^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: methods `next_u32` and `next_bool_u8` are never used
  --> src/main.rs:44:8
   |
38 | impl XorShift32 {
   | --------------- methods in this implementation
...
44 |     fn next_u32(&mut self) -> u32 {
   |        ^^^^^^^^
...
53 |     fn next_bool_u8(&mut self) -> u8 {
   |        ^^^^^^^^^^^^

warning: function `generate_arr` is never used
  --> src/main.rs:59:4
   |
59 | fn generate_arr(rng: &mut XorShift32) -> [u8; 256] {
   |    ^^^^^^^^^^^^

warning: function `generate_arr2` is never used
  --> src/main.rs:68:4
   |
68 | fn generate_arr2(
   |    ^^^^^^^^^^^^^

warning: function `calc_score` is never used
  --> src/main.rs:87:4
   |
87 | fn calc_score(arr: &[u8; 256], constraint: &Vec<(usize, usize, usize, u8, u8, u8)>) -> u32 {
   |    ^^^^^^^^^^

warning: method `isTimeOver` should have a snake c

ソースコード

diff #
raw source code 

use proconio::input;

const N: usize = 2048;
//const N: usize = 24;

// https://zenn.dev/tipstar0125/articles/245bceec86e40a
struct TimeKeeper {
    t_start: std::time::Instant,
    t_threshold: f64,
}
impl TimeKeeper {
    fn new(t_threshold: f64) -> Self {
        TimeKeeper {
            t_start: std::time::Instant::now(),
            t_threshold,
        }
    }
    #[inline]
    fn isTimeOver(&self) -> bool {
        let elapsed_time = self.t_start.elapsed().as_nanos() as f64 * 1e-9;
        #[cfg(feature = "local")]
        {
            elapsed_time * 0.85 >= self.t_threshold
        }
        #[cfg(not(feature = "local"))]
        {
            elapsed_time >= self.t_threshold
        }
    }
}

// XorShift
// https://gemini.google.com/app/3ddaf2f301e50794?utm_source=app_launcher&utm_medium=owned&utm_campaign=base_all
struct XorShift32 {
    state: u32,
}

impl XorShift32 {
    // 初期シード
    fn new(seed: u32) -> Self {
        XorShift32 { state: seed }
    }
    // 次の乱数を生成
    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_bool_u8(&mut self) -> u8 {
        (self.next_u32() & 1) as u8
    }
}

// ランダムに0,1 を256個出力する
fn generate_arr(rng: &mut XorShift32) -> [u8; 256] {
    let mut res = [0_u8; 256];
    for i in 0..256 {
        res[i] = rng.next_bool_u8();
    }
    res
}

// 後ろの制約から決めていく
fn generate_arr2(
    rng: &mut XorShift32,
    constraint: &Vec<(usize, usize, usize, u8, u8, u8)>,
) -> [u8; 256] {
    let mut res = [0_u8; 256];
    for i in (0..N).rev() {
        let &(a, b, c, p, q, r) = &constraint[i];
        let random = rng.next_u32();
        match random % 3 {
            0 => res[a] = p,
            1 => res[b] = q,
            2 => res[c] = r,
            _ => unreachable!(),
        }
    }
    res
}

// スコア計算
fn calc_score(arr: &[u8; 256], constraint: &Vec<(usize, usize, usize, u8, u8, u8)>) -> u32 {
    for i in 0..N {
        let &(a, b, c, p, q, r) = &constraint[i];
        if (arr[a] != p) & (arr[b] != q) & (arr[c] != r) {
            return i as u32;
        }
    }
    N as u32
}

// solver_dfc
// 普通に深さ優先探索するとどうなる？
fn dfs(
    arr: &mut [u8; 256],
    constraint: &Vec<(usize, usize, usize, u8, u8, u8)>,
    i: usize,
    rng: &mut XorShift32,
    timer: &TimeKeeper,
) -> (u32, [u8; 256]) {
    let mut best_score: u32 = i as u32;
    let mut best_arr: [u8; 256] = *arr;
    if timer.isTimeOver() | (i >= N){
        return (best_score, best_arr);
    }
    let &(a, b, c, p, q, r) = &constraint[i];
    // すでに条件達成済み
    if (arr[a] == p) | (arr[b] == q) | (arr[c] == r) {
        return dfs(arr, &constraint, i + 1, rng, &timer);
    } else {
        // ここから条件を動かす
        if arr[a] == 2 {
            arr[a] = p;
            let (score_tmp, arr_tmp) = dfs(arr, constraint, i + 1, rng, timer);
            if score_tmp > best_score {
                best_score = score_tmp;
                best_arr = arr_tmp;
            }
            arr[a] = 2;
        }
        if arr[b] == 2 {
            if timer.isTimeOver() {
                return (best_score, best_arr);
            }
            arr[b] = q;
            let (score_tmp, arr_tmp) = dfs(arr, constraint, i + 1, rng, timer);
            if score_tmp > best_score {
                best_score = score_tmp;
                best_arr = arr_tmp;
            }
            arr[b] = 2;
        }
        if arr[c] == 2 {
            if timer.isTimeOver() {
                return (best_score, best_arr);
            }
            arr[c] = r;
            let (score_tmp, arr_tmp) = dfs(arr, constraint, i + 1, rng, timer);
            if score_tmp > best_score {
                best_score = score_tmp;
                best_arr = arr_tmp;
            }
            arr[c] = 2;
        }
        return (best_score, best_arr);
    }
}

fn main() {
    // タイマー
    let timer = TimeKeeper::new(1.9);
    // 入力
    input! {
        constraint:[(usize, usize, usize, u8,u8,u8);N]
    }

    // 乱数初期化
    let mut rng = XorShift32::new(4869);
    let mut arr = [2_u8; 256];
    let (_, best_arr) = dfs(&mut arr, &constraint, 0, &mut rng, &timer);

    // 出力
    for &a in best_arr.iter().rev() {
        if a == 2 { print!("0") } else { print!("{a}") }
    }
}
0