結果
問題 |
No.5021 Addition Pyramid
|
ユーザー |
|
提出日時 | 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
ソースコード
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); }