#1046125 (Rust) No.5021 Addition Pyramid

• 問題: No.5021 Addition Pyramid
• ユーザー: takumi152
• 提出日時: 2025-02-25 21:31:20
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 1,802 ms / 2,000 ms
• コード長: 8,325 bytes
• コンパイル時間: 13,274 ms
• コンパイル使用メモリ: 398,948 KB
• 実行使用メモリ: 6,824 KB
• スコア: 47,005,510
• 最終ジャッジ日時: 2025-02-25 21:33:18
• 合計ジャッジ時間: 107,134 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

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

コンパイルメッセージ

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(_) => 1e6,
            };
            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<i32>) -> i32 {
            let mut max_diff = 0;
            let mut current_values = values.clone();
            for i in (0..env.board_size).rev() {
                for j in 0..=i {
                    max_diff = max_diff.max(i32::min((env.target_values[i][j] - current_values[j]).abs(), MOD - (env.target_values[i][j] - current_values[j]).abs()));
                }
                for j in 0..i {
                    current_values[j] = (current_values[j] + current_values[j + 1]) % MOD;
                }
            }
            MOD / 2 - max_diff
        }

        let mut values = vec![0; env.board_size];
        for i in 0..env.board_size {
            values[i] = rng.next_i32_mod(MOD as u64);
        }

        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 v = rng.next_i32_mod(MOD as u64);

                let old_v = values[i];
                values[i] = 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
                        values[i] = old_v;
                    }
                }
            }
            else if roll < 1.00 {
                let i = rng.next_u32_mod(env.board_size as u64) as usize;
                let d = rng.next_i32_mod(2001) - 1000;

                let old_v = values[i];
                values[i] = (values[i] + d + MOD) % MOD;

                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
                        values[i] = 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)
    }

    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();
}