#1046176 (Rust) No.5021 Addition Pyramid

• 問題: No.5021 Addition Pyramid
• ユーザー: xyz600600
• 提出日時: 2025-02-25 22:08:02
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 1,904 ms / 2,000 ms
• コード長: 8,995 bytes
• コンパイル時間: 14,502 ms
• コンパイル使用メモリ: 389,628 KB
• 実行使用メモリ: 6,820 KB
• スコア: 25,856,811
• 最終ジャッジ日時: 2025-02-25 22:09:56
• 合計ジャッジ時間: 111,923 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	AC * 50

コンパイルメッセージ

warning: unused variable: `n`
  --> src/main.rs:87:30
   |
87 | fn index(i: usize, j: usize, n: usize) -> usize {
   |                              ^ help: if this is intentional, prefix it with an underscore: `_n`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: field `m` is never read
  --> src/main.rs:11:5
   |
6  | pub struct LcgRng {
   |            ------ field in this struct
...
11 |     m: u64,
   |     ^
   |
   = note: `#[warn(dead_code)]` on by default

warning: field `computed_matrix` is never read
  --> src/main.rs:82:5
   |
80 | struct Solution {
   |        -------- field in this struct
81 |     bottom_row: Vec<i32>,
82 |     computed_matrix: Vec<i32>,
   |     ^^^^^^^^^^^^^^^
   |
   = note: `Solution` has a derived impl for the trait `Clone`, but this is intentionally ignored during dead code analysis

ソースコード

use std::io;
use std::time::Instant;
use std::time::{SystemTime, UNIX_EPOCH};

/// 線形合同法を使用した簡易乱数生成器
pub struct LcgRng {
    state: u64,
    // LCG の定数（Numerical Recipes の値）
    a: u64,
    c: u64,
    m: u64,
}

impl LcgRng {
    /// 現在の時刻をシードにして新しい乱数生成器を作成
    pub fn new() -> Self {
        let seed = SystemTime::now()
            .duration_since(UNIX_EPOCH)
            .unwrap_or_default()
            .as_secs();

        Self::with_seed(seed)
    }

    /// 指定したシードで新しい乱数生成器を作成
    pub fn with_seed(seed: u64) -> Self {
        // シードが0の場合は1にする（一部のLCGでは0が問題になる場合がある）
        let state = if seed == 0 { 1 } else { seed };

        // LCG の定数
        // これらの値はNumerical Recipesの値を使用
        let a: u64 = 6364136223846793005;
        let c: u64 = 1442695040888963407;
        let m: u64 = u64::MAX; // 2^64

        Self { state, a, c, m }
    }

    /// 次の乱数を生成（内部状態を更新）
    fn next(&mut self) -> u64 {
        // (a * X + c) % m の計算
        self.state = self.state.wrapping_mul(self.a).wrapping_add(self.c);
        self.state
    }

    /// 0から指定した最大値（除外）までの範囲の乱数を生成
    pub fn gen_range(&mut self, max: i64) -> i64 {
        if max <= 0 {
            return 0;
        }

        // 次の乱数を取得して範囲内に収める
        let rand_val = self.next();
        (rand_val as i64) % max
    }

    /// 0から指定した最大値（含む）までの範囲の乱数を生成
    pub fn gen_range_inclusive(&mut self, max: i64) -> i64 {
        if max < 0 {
            return 0;
        }

        // 次の乱数を取得して範囲内に収める
        let rand_val = self.next();
        (rand_val as i64) % (max + 1)
    }
}

const MOD: i32 = 100_000_000;
const TIME_LIMIT: u128 = 1900;

// 問題データを保持する構造体
struct Problem {
    n: usize,
    matrix: Vec<i32>,
}

// 解答を表す構造体
#[derive(Clone)]
struct Solution {
    bottom_row: Vec<i32>,
    computed_matrix: Vec<i32>,
    max_error: i32,
}

// ピラミッドの位置を一次元インデックスに変換する関数
fn index(i: usize, j: usize, n: usize) -> usize {
    // 行iまでの要素数の合計 + 列j
    (i * (i + 1)) / 2 + j
}

fn main() {
    // 入力から問題データを読み込む
    let problem = read_problem();

    // 焼きなまし法で問題を解く
    let solution = simulated_annealing(&problem);

    // 解答を出力
    output_solution(&solution);
}

// 標準入力から問題データを読み込む関数
fn read_problem() -> Problem {
    // Nを読み込む
    let n: usize = read_line().trim().parse().expect("Failed to parse N");

    // 一次元配列を用意
    let total_elements = n * (n + 1) / 2;
    let mut matrix = vec![0; total_elements];

    // N行のデータを読み込む
    let mut idx = 0;
    for i in 1..=n {
        let line = read_line();
        let values: Vec<i32> = line
            .split_whitespace()
            .map(|s| s.parse().expect("Failed to parse value"))
            .collect();

        // 各行には i 個の値があるはず
        if values.len() != i {
            panic!("Expected {} values on line {}, but got {}", i, i, values.len());
        }

        for val in values {
            matrix[idx] = val;
            idx += 1;
        }
    }

    Problem { n, matrix }
}

// 標準入力から1行読み込む関数
fn read_line() -> String {
    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("Failed to read line");
    input
}

// 解答を出力する関数
fn output_solution(solution: &Solution) {
    // 最下段の値を出力
    for &value in &solution.bottom_row {
        print!("{} ", value);
    }
    println!();
}

// ピラミッドの計算を行う関数
fn compute_pyramid(bottom_row: &[i32], n: usize) -> Vec<i32> {
    let total_elements = n * (n + 1) / 2;
    let mut pyramid = vec![0; total_elements];

    // 最下段を設定
    for j in 0..n {
        pyramid[index(n - 1, j, n)] = bottom_row[j];
    }

    // 上の段を計算
    for i in (0..n - 1).rev() {
        for j in 0..=i {
            // 下の2つの値を足して MOD を取る
            pyramid[index(i, j, n)] = (pyramid[index(i + 1, j, n)] + pyramid[index(i + 1, j + 1, n)]) % MOD;
        }
    }

    pyramid
}

// 誤差を計算する関数（問題特有の誤差計算方法）
fn calculate_error(a: i32, b: i32) -> i32 {
    let diff = (a - b).abs();
    diff.min(MOD - diff)
}

// 全体の誤差を計算する関数
fn calculate_max_error(computed: &[i32], target: &[i32]) -> i32 {
    let mut max_error = 0;

    for i in 0..computed.len() {
        let error = calculate_error(computed[i], target[i]);
        max_error = max_error.max(error);
    }

    max_error
}

// 初期解を生成する関数
fn initial_solution(problem: &Problem) -> Solution {
    // 最下段を最下行の目標値と同じに設定
    let mut bottom_row = vec![0; problem.n];

    // 最下段の値を取得
    for j in 0..problem.n {
        bottom_row[j] = problem.matrix[index(problem.n - 1, j, problem.n)];
    }

    // ピラミッドを計算
    let computed_matrix = compute_pyramid(&bottom_row, problem.n);

    // 最大誤差を計算
    let max_error = calculate_max_error(&computed_matrix, &problem.matrix);

    Solution {
        bottom_row,
        computed_matrix,
        max_error,
    }
}

// 近傍操作1: 左から交互に (k, -k, 0, k, -k, 0, ...) を足す
fn neighbor_operation1(bottom_row: &mut Vec<i32>, k: i32, shift: usize) {
    for i in 0..bottom_row.len() {
        if (i + shift) % 3 == 0 {
            bottom_row[i] = (bottom_row[i] + k) % MOD;
        } else if (i + shift) % 3 == 1 {
            bottom_row[i] = (bottom_row[i] - k + MOD) % MOD;
        }
        // i % 3 == 2 のときは何もしない
    }
}

// 近傍操作2: 両端に (k, 0, ..., 0, k) を足す
fn neighbor_operation2(bottom_row: &mut Vec<i32>, k: i32) {
    let bottom_len = bottom_row.len();
    if bottom_len >= 2 {
        bottom_row[0] = (bottom_row[0] + k) % MOD;
        bottom_row[bottom_len - 1] = (bottom_row[bottom_len - 1] + k) % MOD;
    }
}

// 焼きなまし法
fn simulated_annealing(problem: &Problem) -> Solution {
    let start_time = Instant::now();
    let mut rng2 = LcgRng::new();

    // 初期解
    let mut current_solution = initial_solution(problem);
    let mut best_solution = current_solution.clone();

    // 初期温度と冷却率
    let mut progress: f64 = 0.0;
    let initial_temp: f64 = 1e5;
    let end_temp: f64 = 1e2;
    let mut temp = initial_temp.powf(1.0 - progress) * end_temp.powf(progress);

    // 焼きなまし法のメインループ
    for turn in 0.. {
        // 現在の解のコピーを作成
        let mut new_bottom_row = current_solution.bottom_row.clone();

        // ランダムに近傍操作を選択
        let op = rng2.gen_range(2) as i32;
        let max = (1e7 * (1.0 - progress) + 1e4 * progress).round() as i64;
        let k = rng2.gen_range(max) as i32 + 1; // 変化量

        if op == 0 {
            let shift = rng2.gen_range(3) as usize;
            neighbor_operation1(&mut new_bottom_row, k, shift);
        } else {
            neighbor_operation2(&mut new_bottom_row, k);
        }

        // 新しいピラミッドを計算
        let new_computed_matrix = compute_pyramid(&new_bottom_row, problem.n);
        let new_max_error = calculate_max_error(&new_computed_matrix, &problem.matrix);

        // 解の評価
        let delta = new_max_error as f64 - current_solution.max_error as f64;

        // より良い解、または確率的に受理される悪い解ならば更新
        let rand = rng2.gen_range(10000_0000) as f64 / 10000_0000.0;
        if delta <= 0.0 || rand < (-delta / temp).exp() {
            current_solution = Solution {
                bottom_row: new_bottom_row,
                computed_matrix: new_computed_matrix,
                max_error: new_max_error,
            };

            // 最良解の更新
            if current_solution.max_error < best_solution.max_error {
                best_solution = current_solution.clone();
            }
        }

        if turn % 128 == 0 {
            let elapsed = start_time.elapsed().as_millis();
            progress = elapsed as f64 / TIME_LIMIT as f64;
            temp = initial_temp.powf(1.0 - progress) * end_temp.powf(progress);

            if elapsed > TIME_LIMIT {
                eprintln!("turn = {}", turn);
                break;
            }
        }
    }

    for i in 0..best_solution.bottom_row.len() {
        best_solution.bottom_row[i] = (best_solution.bottom_row[i] + MOD) % MOD;
    }
    best_solution
}