結果
| 問題 |
No.5021 Addition Pyramid
|
| コンテスト | |
| ユーザー |
 Keroru
|
| 提出日時 | 2025-02-25 23:00:00 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,988 ms / 2,000 ms |
| コード長 | 6,669 bytes |
| コンパイル時間 | 12,859 ms |
| コンパイル使用メモリ | 405,572 KB |
| 実行使用メモリ | 71,248 KB |
| スコア | 265,923,712 |
| 最終ジャッジ日時 | 2025-02-25 23:02:52 |
| 合計ジャッジ時間 | 113,485 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge7 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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 = 42;
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);
}