結果
| 問題 |
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
}