結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー Keroru
提出日時 2025-02-25 22:14:05
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,698 ms / 2,000 ms
コード長 5,841 bytes
コンパイル時間 13,783 ms
コンパイル使用メモリ 385,688 KB
実行使用メモリ 31,328 KB
スコア 221,918,308
最終ジャッジ日時 2025-02-25 22:15:47
合計ジャッジ時間 98,294 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge7
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::cmp::{min, max};
use std::io::{self, BufRead};

const MOD: i32 = 100_000_000;

fn error(x: u32, y: u32) -> u32 {
    let diff = if x > y { x - y } else { y - x };
    min(diff, (MOD as u32).saturating_sub(diff))
}

/// 上段 prev_row から，新たな行 new_row（長さ = prev_row.len() + 1）を，
/// pivot_index 番目の値 pivot_val を自由変数として左右に順次決定して返す．
fn compute_row(prev_row: &Vec<u32>, pivot_index: usize, pivot_val: u32) -> Vec<u32> {
    let n = prev_row.len();
    let l = n + 1;
    let mut new_row = vec![0u32; l];
    new_row[pivot_index] = pivot_val;
    // 右側を決定: new_row[j+1] = (prev_row[j] - new_row[j]) mod MOD
    for j in pivot_index..(l - 1) {
        let diff = (prev_row[j] as i32 - new_row[j] as i32).rem_euclid(MOD);
        new_row[j + 1] = diff as u32;
    }
    // 左側を決定: new_row[j-1] = (prev_row[j-1] - new_row[j]) mod MOD
    for j in (1..=pivot_index).rev() {
        let diff = (prev_row[j - 1] as i32 - new_row[j] as i32).rem_euclid(MOD);
        new_row[j - 1] = diff as u32;
    }
    new_row
}

/// rli: [start, end] の範囲を，count 個の値に等間隔（小数点は四捨五入）で分割した値を返す．
fn rli(count: usize, start: i32, end: i32) -> Vec<i32> {
    let mut result = Vec::with_capacity(count);
    if count == 1 {
        result.push((start + end) / 2);
    } else {
        let step = (end - start) as f64 / (count - 1) as f64;
        for i in 0..count {
            let value = start as f64 + step * i as f64;
            result.push(value.round() as i32);
        }
    }
    result
}

/// beam_search
/// - a: 目標ピラミッド．a[i] は第 i+1 段（0-indexed）の目標値ベクトル（長さ = i+1）
/// - beam_width: 各段で保持する候補数
/// - delta_range: 自由変数（中央のセル）の候補として，ターゲット値からのずれ [-delta_range, delta_range] を試す
/// - cand_num: 各段で自由変数に対して試す候補数（等間隔にサンプリング）
///
/// 各候補は (current_row, current_max_err) のタプルで保持され，
/// current_max_err はこれまでの段での最大誤差．
/// 最終的に (底辺, max_error) のタプルを返す．
fn beam_search(a: &Vec<Vec<u32>>, beam_width: usize, delta_range: i32, cand_num: usize) -> (Vec<u32>, u32) {
    let n = a.len();
    // 初期ビーム: 第1段は [a[0][0]] だが，
    // 自由変数として a[0][0] - delta (delta ∈ RLI(beam_width, -delta_range, delta_range)) を候補とする
    let mut beam: Vec<(Vec<u32>, u32)> = Vec::new();
    for delta in rli(beam_width, -delta_range, delta_range) {
        let candidate_val = ((a[0][0] as i32 - delta).rem_euclid(MOD)) as u32;
        beam.push((vec![candidate_val], delta.abs() as u32));
    }
    // 各段を順次拡張していく（i = 1..n-1）
    for i in 1..n {
        let mut new_beam: Vec<(Vec<u32>, u32)> = Vec::new();
        let l = i + 1;
        // 新たな行の自由変数として中央 (1-indexed で (l+1)//2 番目) を使う
        let pivot_index = (l + 1) / 2 - 1;
        for (row, curr_max_err) in &beam {
            let target_pivot = a[i][pivot_index];
            // ターゲット値の前後 delta_range 内の候補（cand_num 個）を試す
            for delta in rli(cand_num, -delta_range, delta_range) {
                let pivot_val = ((target_pivot as i32 + delta).rem_euclid(MOD)) as u32;
                let new_row = compute_row(row, pivot_index, pivot_val);
                // 新たな行における各セルの誤差を計算
                let mut row_max_err = 0u32;
                for j in 0..l {
                    row_max_err = max(row_max_err, error(new_row[j], a[i][j]));
                }
                let new_max_err = max(*curr_max_err, row_max_err);
                new_beam.push((new_row, new_max_err));
            }
        }
        // 評価（最大誤差）の小さい順にソートして、beam_width 個だけ残す
        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());
    // 最初の行は 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 = 280;
    let delta_range = 8000000;
    let cand_num = beam_width;
    let (bottom_row, best_err) = beam_search(&a, beam_width, delta_range, cand_num);
    // スコアは 5×10⁷ - best_err とする
    let score = 50_000_000 - best_err as i32;
    eprintln!("Score: {}", score*50);
    // 底辺の各値を 1 行ずつ出力
    let output_line = bottom_row.iter()
                                .map(|num| num.to_string())
                                .collect::<Vec<_>>()
                                .join(" ");
    println!("{}", output_line);
}
0