結果
| 問題 |
No.5021 Addition Pyramid
|
| コンテスト | |
| ユーザー |
 takumi152
|
| 提出日時 | 2025-02-25 22:34:46 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,804 ms / 2,000 ms |
| コード長 | 9,245 bytes |
| コンパイル時間 | 11,398 ms |
| コンパイル使用メモリ | 403,588 KB |
| 実行使用メモリ | 6,824 KB |
| スコア | 48,209,388 |
| 最終ジャッジ日時 | 2025-02-25 22:36:33 |
| 合計ジャッジ時間 | 105,643 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
warning: variable does not need to be mutable
--> src/main.rs:147:17
|
147 | let mut current_values = values.clone();
| ----^^^^^^^^^^^^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: methods `next_u16_mod`, `next_i16_mod`, and `next_u64` are never used
--> src/main.rs:17:16
|
6 | impl Xorshift64 {
| --------------- methods in this implementation
...
17 | pub fn next_u16_mod(&mut self, modulo: u64) -> u16 {
| ^^^^^^^^^^^^
...
21 | pub fn next_i16_mod(&mut self, modulo: u64) -> i16 {
| ^^^^^^^^^^^^
...
33 | pub fn next_u64(&mut self) -> u64 {
| ^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
ソースコード
mod lib {
pub struct Xorshift64 {
x: u64
}
impl Xorshift64 {
pub fn new(seed: u64) -> Self {
Self { x: seed }
}
fn next(&mut self) -> u64 {
self.x ^= self.x << 7;
self.x ^= self.x >> 9;
self.x
}
pub fn next_u16_mod(&mut self, modulo: u64) -> u16 {
(((self.next() & 0x0000ffffffffffff) * modulo) >> 48) as u16
}
pub fn next_i16_mod(&mut self, modulo: u64) -> i16 {
(((self.next() & 0x0000ffffffffffff) * modulo) >> 48) as i16
}
pub fn next_u32_mod(&mut self, modulo: u64) -> u32 {
(((self.next() & 0x00000000ffffffff) * modulo) >> 32) as u32
}
pub fn next_i32_mod(&mut self, modulo: u64) -> i32 {
(((self.next() & 0x00000000ffffffff) * modulo) >> 32) as i32
}
pub fn next_u64(&mut self) -> u64 {
self.next()
}
pub fn next_f64(&mut self) -> f64 {
(self.next() as f64) * 5.42101086242752217e-20
}
}
}
mod solver {
use std::{
env, io::{self, BufReader}, time::Instant
};
use proconio::{input, source::line::LineSource};
use super::lib::Xorshift64;
const MOD: i32 = 100_000_000;
pub struct HyperParameter {
pub sa_base_temperature: f64,
pub sa_target_temperature: f64,
}
impl HyperParameter {
pub fn new() -> Self {
let sa_base_temperature = match env::var("AHC_SA_BASE_TEMPERATURE") {
Ok(val) => val.parse().unwrap(),
Err(_) => 1e2,
};
let sa_target_temperature = match env::var("AHC_SA_TARGET_TEMPERATURE") {
Ok(val) => val.parse().unwrap(),
Err(_) => 1e0,
};
Self {
sa_base_temperature,
sa_target_temperature
}
}
}
pub struct Input {
pub board_size: usize,
pub target_values: Vec<Vec<i32>>,
}
impl Input {
pub fn new(board_size: usize, target_values: Vec<Vec<i32>>) -> Self {
Self { board_size, target_values }
}
pub fn from_stdin() -> Self {
// magic
let mut stdin = LineSource::new(BufReader::new(io::stdin()));
macro_rules! input(($($tt:tt)*) => (proconio::input!(from &mut stdin, $($tt)*)));
input! {
board_size: usize,
}
let mut target_values = vec![vec![-1; board_size]; board_size];
for i in 0..board_size {
for j in 0..=i {
input! {
target_value: i32,
}
target_values[i][j] = target_value;
}
}
Self::new(board_size, target_values)
}
}
pub struct Output {
pub values: Vec<i32>
}
impl Output {
pub fn new(values: Vec<i32>) -> Self {
Self { values }
}
pub fn output(&self) {
for i in 0..self.values.len() {
print!("{} ", self.values[i]);
}
println!();
}
}
pub struct Env {
pub time_begin: Instant,
pub board_size: usize,
pub target_values: Vec<Vec<i32>>,
}
impl Env {
pub fn new(input: Input) -> Self {
let time_begin = Instant::now();
Self {
time_begin,
board_size: input.board_size,
target_values: input.target_values,
}
}
}
pub fn solve_sa(env: &Env, hyp_param: &HyperParameter, rng: &mut Xorshift64, time_limit: f64) -> Output {
fn calc_score_full(env: &Env, values: &Vec<Vec<i32>>) -> i32 {
let mut max_diff = 0;
let mut current_values = values.clone();
for i in 0..env.board_size {
for j in 0..=i {
max_diff = max_diff.max(i32::min((env.target_values[i][j] - current_values[i][j]).abs(), MOD - (env.target_values[i][j] - current_values[i][j]).abs()));
}
}
MOD / 2 - max_diff
}
fn update_values(env: &Env, values: &mut Vec<Vec<i32>>, i: usize, j: usize, v: i32) {
values[i][j] = v;
for k in (0..i).rev() {
for l in 0..=j.min(k) {
values[k][l] = (values[k + 1][l] + values[k + 1][l + 1]) % MOD;
}
}
for k in i+1..env.board_size {
for l in j..k {
values[k][l + 1] = (values[k - 1][l] - values[k][l] + MOD) % MOD;
}
}
}
let mut values = vec![vec![-1; env.board_size]; env.board_size];
for i in 0..env.board_size {
values[env.board_size - 1][i] = env.target_values[env.board_size - 1][i];
}
for i in (0..env.board_size - 1).rev() {
for j in 0..=i {
values[i][j] = (values[i + 1][j] + values[i + 1][j + 1]) % MOD;
}
}
let mut last_score = calc_score_full(env, &values);
let mut best_score = last_score;
let base_temperature = hyp_param.sa_base_temperature;
let target_temperature = hyp_param.sa_target_temperature;
let mut temperature = base_temperature;
let mut iter_count = 0;
let time_start = Instant::now();
let mut progress;
loop {
if iter_count % 128 == 0 {
let time_now = Instant::now();
let time_since_program_start = time_now.duration_since(env.time_begin);
if time_since_program_start.as_secs_f64() > time_limit {
break;
}
let current_time = time_now.duration_since(time_start);
progress = (current_time.as_secs_f64() / (time_limit - time_start.duration_since(env.time_begin).as_secs_f64())).min(1.0);
temperature = (base_temperature.ln() - (base_temperature.ln() - target_temperature.ln()) * progress).exp();
}
let roll = rng.next_f64();
if roll < 0.50 {
let i = rng.next_u32_mod(env.board_size as u64) as usize;
let j = rng.next_u32_mod((i + 1) as u64) as usize;
let v = rng.next_i32_mod(MOD as u64);
let old_v = values[i][j];
update_values(env, &mut values, i, j, v);
let score = calc_score_full(env, &values);
if score >= last_score {
last_score = score;
if score > best_score {
best_score = score;
}
}
else {
let delta = (score - last_score) as f64;
let prob = (delta / temperature).exp();
if rng.next_f64() < prob { // accept
last_score = score;
}
else { // rollback
update_values(env, &mut values, i, j, old_v);
}
}
}
else if roll < 1.00 {
let i = rng.next_u32_mod(env.board_size as u64) as usize;
let j = rng.next_u32_mod((i + 1) as u64) as usize;
let d = rng.next_i32_mod(21) - 10;
let old_v = values[i][j];
let v = (values[i][j] + d + MOD) % MOD;
update_values(env, &mut values, i, j, v);
let score = calc_score_full(env, &values);
if score >= last_score {
last_score = score;
if score > best_score {
best_score = score;
}
}
else {
let delta = (score - last_score) as f64;
let prob = (delta / temperature).exp();
if rng.next_f64() < prob { // accept
last_score = score;
}
else { // rollback
update_values(env, &mut values, i, j, old_v);
}
}
}
if iter_count % 10000 == 0 {
eprintln!("iter: {:>8}, last_score: {:>8}, best_score: {:>8}, temperature: {}", iter_count, last_score, best_score, temperature);
}
iter_count += 1;
}
eprintln!("iter_count = {}", iter_count);
eprintln!("last_score = {}", last_score);
eprintln!("best_score = {}", best_score);
eprintln!("temperature = {}", temperature);
Output::new(values[env.board_size - 1].clone())
}
pub fn solve(env: &Env) -> Output {
let hyp_param = HyperParameter::new();
let mut rng = Xorshift64::new(88172645463325252);
solve_sa(env, &hyp_param, &mut rng, 1.8)
}
pub fn run() {
let input = Input::from_stdin();
let env = Env::new(input);
let output = solve(&env);
output.output();
}
}
fn main() {
solver::run();
}