結果

問題 No.5021 Addition Pyramid
ユーザー Keroru
提出日時 2025-02-25 22:54:20
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,785 ms / 2,000 ms
コード長 6,669 bytes
コンパイル時間 12,280 ms
コンパイル使用メモリ 402,260 KB
実行使用メモリ 66,456 KB
スコア 258,745,558
最終ジャッジ日時 2025-02-25 22:56:57
合計ジャッジ時間 100,329 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `Write`
 --> src/main.rs:2:30
  |
2 | use std::io::{self, BufRead, Write};
  |                              ^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: method `to_vec` is never used
  --> src/main.rs:51:8
   |
43 | impl Row {
   | -------- method in this implementation
...
51 |     fn to_vec(&self) -> Vec<u32> {
   |        ^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff #

use std::cmp::{min, max};
use std::io::{self, BufRead, Write};
use std::time::{SystemTime, UNIX_EPOCH};

const MOD: i32 = 100_000_000;

// xorshift による乱数生成器(RLI用)
struct XorShiftRng {
    state: u64,
}

impl XorShiftRng {
    fn new(seed: u64) -> Self {
        XorShiftRng { state: seed }
    }
    #[inline(always)]
    fn next_u32(&mut self) -> u32 {
        self.state ^= self.state << 13;
        self.state ^= self.state >> 7;
        self.state ^= self.state << 17;
        (self.state & 0xFFFF_FFFF) as u32
    }
}

/// rli: [start, end] の範囲から、一様乱数を count 個生成して返す(両端含む)
fn rli(rng: &mut XorShiftRng, count: usize, start: i32, end: i32) -> Vec<i32> {
    let mut result = Vec::with_capacity(count);
    let range = (end - start + 1) as u32; // [start, end] を含む
    for _ in 0..count {
        let r = (rng.next_u32() % range) as i32 + start;
        result.push(r);
    }
    result
}

// 固定長配列と長さで行を保持する構造体
#[derive(Clone)]
struct Row {
    data: [u32; 64],
    len: usize,
}

impl Row {
    #[inline(always)]
    fn new_single(val: u32) -> Self {
        let mut data = [0u32; 64];
        data[0] = val;
        Row { data, len: 1 }
    }
    // 出力用:先頭 len 要素を Vec<u32> に変換
    fn to_vec(&self) -> Vec<u32> {
        self.data[..self.len].to_vec()
    }
}

#[inline(always)]
fn error_value(x: u32, y: u32) -> u32 {
    let diff = if x > y { x - y } else { y - x };
    min(diff, (MOD as u32).saturating_sub(diff))
}

/// 与えられた上段 prev から、新たな行 new_row(長さ = prev.len + 1)を、
/// 指定位置 pivot_index に自由変数 pivot_val を置き、左右を決定して返す.
#[inline(always)]
fn compute_row(prev: &Row, pivot_index: usize, pivot_val: u32) -> Row {
    let new_len = prev.len + 1;
    let mut new_data = [0u32; 64];
    new_data[pivot_index] = pivot_val;
    // 右側を決定: new_data[j+1] = (prev.data[j] - new_data[j]) mod MOD
    for j in pivot_index..(new_len - 1) {
        let diff = (prev.data[j] as i32 - new_data[j] as i32).rem_euclid(MOD);
        new_data[j + 1] = diff as u32;
    }
    // 左側を決定: new_data[j-1] = (prev.data[j-1] - new_data[j]) mod MOD
    for j in (1..=pivot_index).rev() {
        let diff = (prev.data[j - 1] as i32 - new_data[j] as i32).rem_euclid(MOD);
        new_data[j - 1] = diff as u32;
    }
    Row { data: new_data, len: new_len }
}

/// beam_search
/// - a: 目標ピラミッド. a[i] は第 \(i+1\) 段(0-indexed)の目標値ベクトル(長さ = i+1)
/// - beam_width: 各段で保持する候補数
/// - delta_range: 自由変数の候補として、ターゲット値からのずれ \([-delta\_range, delta\_range]\) を試す
/// - cand_num: 各段で自由変数に対して試す候補数(乱数でサンプリング)
///
/// 各候補は (Row, current_max_error) として保持し、最終的に (底辺, max_error) を返す.
fn beam_search(a: &Vec<Vec<u32>>, beam_width: usize, delta_range: i32, cand_num: usize) -> (Row, u32) {
    let n = a.len();
    // 乱数初期化(現在時刻をシードに)
    let seed = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .unwrap()
        .as_secs();
    let mut rng = XorShiftRng::new(seed);
    // 初期ビーム: 第1段は [a[0][0]] だが、候補は a[0][0] - delta, delta ∈ rli(beam_width, -delta_range, delta_range)
    let init_deltas = rli(&mut rng, beam_width, -delta_range, delta_range);
    let mut beam: Vec<(Row, u32)> = Vec::with_capacity(beam_width);
    for delta in init_deltas {
        let candidate_val = ((a[0][0] as i32 - delta).rem_euclid(MOD)) as u32;
        beam.push((Row::new_single(candidate_val), delta.abs() as u32));
    }
    // 各段 (i = 1..n-1) を拡張
    for i in 1..n {
        let new_len = i + 1;
        // 各段では、自由変数を新行の全位置(0~new_len-1)で試す
        let cand_deltas = rli(&mut rng, cand_num, -delta_range, delta_range);
        let mut new_beam: Vec<(Row, u32)> = Vec::new();
        for (prev_row, curr_max_err) in &beam {
            for p in 0..new_len {
                let target = a[i][p];
                for delta in &cand_deltas {
                    let pivot_val = ((target as i32 + delta).rem_euclid(MOD)) as u32;
                    let new_row = compute_row(prev_row, p, pivot_val);
                    // 各セルの誤差を計算
                    let mut row_max_err = 0u32;
                    for j in 0..new_len {
                        row_max_err = max(row_max_err, error_value(new_row.data[j], a[i][j]));
                    }
                    let new_max_err = max(*curr_max_err, row_max_err);
                    new_beam.push((new_row, new_max_err));
                }
            }
        }
        new_beam.sort_by_key(|candidate| candidate.1);
        if new_beam.len() > beam_width {
            new_beam.truncate(beam_width);
        }
        beam = new_beam;
    }
    // 最終段で最小誤差の候補を返す
    beam.into_iter().min_by_key(|candidate| candidate.1).unwrap()
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines().map(|l| l.unwrap());
    // 1行目は N
    let n: usize = lines.next().unwrap().trim().parse().expect("failed to parse N");
    let mut a: Vec<Vec<u32>> = Vec::with_capacity(n);
    // 各段 i (1-indexed) は i 個の整数
    for i in 1..=n {
        let mut row: Vec<u32> = Vec::with_capacity(i);
        while row.len() < i {
            if let Some(line) = lines.next() {
                for token in line.split_whitespace() {
                    if row.len() < i {
                        let num: u32 = token.parse().expect("failed to parse number");
                        row.push(num);
                    }
                }
            } else {
                break;
            }
        }
        a.push(row);
    }
    // パラメータ(必要に応じて調整)
    let beam_width = 40;
    let delta_range = 8_000_000;
    let cand_num = beam_width; // 各段での候補数
    let (bottom_row, best_err) = beam_search(&a, beam_width, delta_range, cand_num);
    // スコアは 5×10⁷ - best_err とする(例:最終スコアとして 50 倍して出力)
    let score = 50_000_000 - best_err as i32;
    eprintln!("Score: {}", score * 50);
    // 底辺の各値を空白区切りで1行に出力
    let output_line = bottom_row.data[..bottom_row.len]
        .iter()
        .map(|num| num.to_string())
        .collect::<Vec<_>>()
        .join(" ");
    println!("{}", output_line);
}
0