Submission #17148236

---

Source Code Expand

#![allow(non_snake_case, unused)]

use proconio::input;
use rand::prelude::*;
use rand_pcg::Mcg128Xsl64;
use std::fs::File;
use std::io::prelude::*;

// utility --------------------------------------------------

// vecのas usizeを避けるためのトレイト
trait IndexAt<T> {
    fn at(&self, i: i32) -> T;
    fn mt(&mut self, i: i32) -> &mut T;
}

trait IndexAt2<T> {
    fn at(&self, i1: i32, i2: i32) -> T;
    fn mt(&mut self, i1: i32, i2: i32) -> &mut T;
}

impl<T: Copy> IndexAt<T> for Vec<T> {
    fn at(&self, i: i32) -> T {
        self[i as usize]
    }
    fn mt(&mut self, i: i32) -> &mut T {
        &mut self[i as usize]
    }
}

impl<T: Copy> IndexAt2<T> for Vec<Vec<T>> {
    fn at(&self, i1: i32, i2: i32) -> T {
        self[i1 as usize][i2 as usize]
    }
    fn mt(&mut self, i1: i32, i2: i32) -> &mut T {
        &mut self[i1 as usize][i2 as usize]
    }
}

static mut START_TIME: f64 = -1.0;
pub fn get_time() -> f64 {
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if START_TIME < 0.0 {
            START_TIME = ms;
        }
        ms - START_TIME
    }
}

#[cfg(feature = "local")]
use log::{debug, error, info, warn, LevelFilter};

struct Logger {}

#[cfg(feature = "local")]
impl Logger {
    fn init() -> () {
        let log_path = "log/log_main.log";
        use std::fs;
        use std::path::Path;
        if Path::new(log_path).exists() {
            fs::remove_file(log_path).unwrap_or(());
        }
        use log::LevelFilter;
        use log4rs::append::console::ConsoleAppender;
        use log4rs::append::file::FileAppender;
        use log4rs::config::{Appender, Config, Logger, Root};
        use log4rs::encode::pattern::PatternEncoder;
        use log4rs::filter::threshold::ThresholdFilter;

        let stdout = ConsoleAppender::builder().build();
        let fileout = FileAppender::builder()
            .encoder(Box::new(PatternEncoder::new("{d} - {m}{n}")))
            .build(log_path)
            .unwrap();
        let config = Config::builder()
            .appender(
                Appender::builder()
                    .filter(Box::new(ThresholdFilter::new(log::LevelFilter::Info)))
                    .build("stdout", Box::new(stdout)),
            )
            .appender(
                Appender::builder()
                    .filter(Box::new(ThresholdFilter::new(log::LevelFilter::Debug)))
                    .build("fileout", Box::new(fileout)),
            )
            .build(
                Root::builder()
                    .appender("stdout")
                    .appender("fileout")
                    .build(LevelFilter::Debug),
            )
            .unwrap();
        let handle = log4rs::init_config(config).unwrap();
    }
    fn debug(message: String) -> () {
        debug!("{}", message);
    }
    fn info(message: String) -> () {
        info!("{}", message);
    }
    fn error(message: String) -> () {
        error!("{}", message);
    }
}

#[cfg(not(feature = "local"))]
impl Logger {
    fn init() -> () {}
    fn debug(message: String) -> () {}
    fn info(message: String) -> () {}
    fn error(message: String) -> () {}
}

// config --------------------------------------------------
#[derive(Default)]
struct Config {
    is_local: bool,
    is_debug: bool,
    p1: f64,
    time_limit: f64,
}

// main --------------------------------------------------
fn main() -> std::io::Result<()> {
    use std::env;
    env::set_var("RUST_BACKTRACE", "1");

    // Config
    let mut config: Config = Default::default();
    config.is_local = cfg!(feature = "local");
    config.is_debug = false;
    config.p1 = 0.5;
    config.time_limit = 1.8;

    Logger::init();
    get_time();
    let input = Input::create(&mut config);
    let solver = Solver::new(input, &mut config);
    solver.solve();
    Ok(())
}

// input --------------------------------------------------
#[macro_export]
macro_rules! input_value {
    ($f: expr, $x: expr) => {
        let mut line = String::new();
        $f.read_line(&mut line).unwrap();
        $x = line.trim().parse().unwrap();
    };
}

#[macro_export]
macro_rules! input_vec {
    ($f: expr, $x: expr) => {
        let mut line = String::new();
        $f.read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        $x = iter.map(|v| v.parse().unwrap()).collect();
    };
}

struct Input {
    D: i32,
    C: Vec<i32>,
    S: Vec<Vec<i32>>,
}

impl Input {
    fn create(config: &mut Config) -> Input {
        use std::fs;
        use std::io::{self, BufRead, BufReader};

        let Z = 26;
        let mut D: i32;
        let mut C: Vec<i32>;
        let mut S: Vec<Vec<i32>>;
        let mut f = BufReader::new(io::stdin());

        let mut f: Box<dyn std::io::BufRead>;
        if config.is_local {
            f = Box::new(BufReader::new(File::open("input/input_02.txt").unwrap()));
        } else {
            f = Box::new(BufReader::new(std::io::stdin()));
        }

        input_value! {f, D}
        input_vec! {f, C}

        S = Default::default();
        for i in 0..D {
            let x: Vec<i32>;
            input_vec! {f, x}
            S.push(x);
        }

        Input { D, C, S }
    }
}

// solve --------------------------------------------------

#[derive(Debug)]
enum Action {
    Swap { action: ActionSwap },
    Change { action: ActionChange },
}

#[derive(Debug, Copy, Clone)]
struct ActionSwap {
    d1: i32,
    d2: i32,
}

#[derive(Debug, Copy, Clone)]
struct ActionChange {
    d: i32,
    k: i32,
}

struct Solver<'a> {
    D: i32,
    C: Vec<i32>,
    S: Vec<Vec<i32>>,
    K: i32,
    config: &'a Config,
}

impl Solver<'_> {
    pub fn new(input: Input, config: &mut Config) -> Solver {
        let K = 26;
        Solver {
            D: input.D,
            C: input.C,
            S: input.S,
            K,
            config,
        }
    }

    pub fn solve(&self) -> () {
        // parameters
        let seed = 71;
        let t0 = 2000.0;
        let t1 = 600.0;

        let mut rng = rand_pcg::Pcg64Mcg::seed_from_u64(seed);
        let mut annealer = Annealer::new(t0, t1);

        let mut command: Vec<i32> = Default::default();
        for i in 0..self.D {
            command.push(rng.gen_range(0, self.K));
        }
        let mut state = State::new(self, command);
        state.initialize();

        let mut counter = 0;
        let mut counter_update = 0;
        let mut best_score = state.score;
        let mut best_command: Vec<i32> = state.command.clone();
        let mut elapsed = 0.0;
        Logger::info(format!("first -- {}", best_score));

        while get_time() < self.config.time_limit {
            loop {
                if counter & 0xFF == 0 {
                    elapsed = get_time();
                    if elapsed > self.config.time_limit {
                        Logger::info(format!("turn:{} best_score:{}", counter, best_score));
                        break;
                    }
                    let anneal_t = elapsed / self.config.time_limit;
                    annealer.set_temperature(anneal_t);
                    if counter & 0xFFFF == 0 {
                        Logger::info(format!(
                            "turn:{} anneal_t:{} temperature:{}",
                            counter, anneal_t, annealer.temperature
                        ));
                    }
                }

                let action: Action;
                let mut new_score: i32;
                if rng.gen::<f64>() < self.config.p1 {
                    // swap
                    let mut d1: i32;
                    let mut d2: i32;
                    loop {
                        let next_range = 16;
                        d1 = rng.gen_range(0, self.D);
                        d2 = d1 + 1 + rng.gen_range(0, next_range);
                        let mut valid = true;
                        if d2 >= self.D || state.command.at(d1) == state.command.at(d2) {
                            valid = false
                        }
                        if valid {
                            break;
                        }
                    }
                    action = Action::Swap {
                        action: ActionSwap { d1, d2 },
                    };
                } else {
                    let mut d: i32;
                    let mut k: i32;
                    // update
                    loop {
                        d = rng.gen_range(0, self.D);
                        k = rng.gen_range(0, self.K);
                        let mut valid = true;
                        if state.command.at(d) == k {
                            valid = false;
                        }
                        if valid {
                            break;
                        }
                    }
                    action = Action::Change {
                        action: ActionChange { d, k },
                    };
                }

                new_score = match action {
                    Action::Swap { action } => state.score_swap(action),
                    Action::Change { action } => state.score_change(action),
                };

                if annealer.accept(state.score, new_score) {
                    counter_update += 1;

                    match action {
                        Action::Swap { action } => state.update_swap(action),
                        Action::Change { action } => state.update_change(action),
                    }

                    Logger::debug(format!(
                        "accepted score: {} turn:{} action:{:?} time:{}",
                        state.score, counter, action, elapsed
                    ));

                    // ベスト点数を超えている場合はその状態を保存
                    if state.score > best_score {
                        best_score = state.score;
                        best_command = state.command.clone();
                        Logger::info(format!("score:{} at turn:{}", best_score, counter));
                    }
                }
                counter += 1;
            }
        }
        eprintln!(
            "counter: {} update:{} best_score:{}",
            counter, counter_update, best_score
        );
        if !self.config.is_local {
            for i in 0..self.D {
                println!("{}", state.command.at(i) + 1);
            }
        }
    }
}

struct Annealer {
    t0: f64,
    t1: f64,
    temperature: f64,
    rng: Mcg128Xsl64,
}

impl Annealer {
    fn new(t0: f64, t1: f64) -> Annealer {
        let seed = 123;
        let rng = rand_pcg::Pcg64Mcg::seed_from_u64(seed);
        Annealer {
            t0,
            t1,
            temperature: t0,
            rng,
        }
    }

    fn set_temperature(&mut self, t: f64) -> () {
        // 指数関数型
        self.temperature = self.t0.powf(1.0 - t) * self.t1.powf(t);
    }

    fn accept(&mut self, prev: i32, curr: i32) -> bool {
        if curr >= prev {
            return true;
        }
        let loss = (curr - prev) as f64;
        let prob = (loss / self.temperature).exp();
        return self.rng.gen_bool(prob);
    }
}

struct State<'a> {
    D: i32,
    K: i32,
    C: &'a Vec<i32>,
    S: &'a Vec<Vec<i32>>,
    command: Vec<i32>,
    score: i32,
    last_contest: Vec<Vec<i32>>, // 前のコンテストの日、初期値は-1
    next_contest: Vec<Vec<i32>>, // 次のコンテストの日、初期値はD
}

impl State<'_> {
    pub fn new<'a>(solver: &'a Solver, command: Vec<i32>) -> State<'a> {
        let D = solver.D;
        let score = 0;
        let mut last_contest: Vec<Vec<i32>> = Vec::new();
        for i in 0..D {
            let mut v = Vec::new();
            v.resize(solver.K as usize, -1);
            last_contest.push(v);
        }
        let mut next_contest: Vec<Vec<i32>> = Vec::new();
        for i in 0..D {
            let mut v = Vec::new();
            v.resize(solver.K as usize, D);
            next_contest.push(v);
        }
        State {
            D: solver.D,
            K: solver.K,
            C: &solver.C,
            S: &solver.S,
            command,
            score,
            last_contest,
            next_contest,
        }
    }

    pub fn initialize(&mut self) -> () {
        self.score = self.score_calc_raw();

        // 初期化
        let mut last_contest: Vec<Vec<i32>> = Vec::new();
        let mut next_contest: Vec<Vec<i32>> = Vec::new();
        for d in 0..self.D {
            let mut v = Vec::new();
            v.resize(self.K as usize, 0);
            last_contest.push(v);
            let mut v = Vec::new();
            v.resize(self.K as usize, 0);
            next_contest.push(v);
        }

        for k in 0..self.K {
            let mut last = -1;
            for d in 0..self.D {
                *last_contest.mt(d, k) = last;
                if self.command.at(d) == k {
                    last = d;
                }
            }
            let mut next = self.D;
            for d in (0..self.D).rev() {
                *next_contest.mt(d, k) = next;
                if self.command.at(d) == k {
                    next = d;
                }
            }
        }

        self.last_contest = last_contest;
        self.next_contest = next_contest;
    }

    pub fn score_calc_raw(&self) -> i32 {
        // 素朴な方法でスコア計算
        let mut score_contests: Vec<i32> = Vec::new();
        score_contests.resize(self.K as usize, 0);

        for k in 0..self.K {
            let mut score_k = 0;
            let mut last = 0;
            for d in 0..self.D {
                if k == self.command.at(d) {
                    score_k += self.S.at(d, k);
                    last = d + 1;
                }
                score_k -= (d + 1 - last) * self.C.at(k);
            }
            *score_contests.mt(k) = score_k;
        }
        score_contests.iter().sum()
    }

    pub fn score_swap(&self, action: ActionSwap) -> i32 {
        // 交換でのスコア試算
        // d1にあるコンテスト: k1 -> k2
        // d2にあるコンテスト: k2 -> k1
        let (d1, d2) = (action.d1, action.d2);
        let k1 = self.command.at(d1);
        let k2 = self.command.at(d2);
        debug_assert_ne!(k1, k2);

        // 差分計算
        let mut diff = 0;
        diff += self.diff_score_swap(k1, d1, d2);
        diff += self.diff_score_swap(k2, d2, d1);

        self.score + diff
    }

    pub fn score_change(&self, action: ActionChange) -> i32 {
        // 変更でのスコア試算
        // dにあるコンテスト: kb -> k
        let (d, k) = (action.d, action.k);
        let kb = self.command.at(d);
        debug_assert_ne!(kb, k);

        // 差分計算
        let mut diff = 0;
        diff += self.diff_score_remove(d, kb);
        diff += self.diff_score_add(d, k);

        self.score + diff
    }

    pub fn update_swap(&mut self, action: ActionSwap) -> () {
        // 交換のアップデート
        let (d1, d2) = (action.d1, action.d2);
        let k1 = self.command.at(d1);
        let k2 = self.command.at(d2);
        debug_assert_ne!(k1, k2);
        self.update_swap_single(k1, d1, d2);
        self.update_swap_single(k2, d2, d1);
        debug_assert_eq!(self.score, self.score_calc_raw())
    }

    pub fn update_change(&mut self, action: ActionChange) -> () {
        // 変更のアップデート
        let (d, k) = (action.d, action.k);
        let kb = self.command.at(d);
        debug_assert_ne!(kb, k);
        self.update_remove(d, kb);
        self.update_add(d, k);
        debug_assert_eq!(self.score, self.score_calc_raw())
    }

    fn diff_score_remove(&self, d: i32, k: i32) -> i32 {
        // コンテスト削除時の差分
        let mut diff = 0;
        diff -= self.S.at(d, k);
        let db1 = (d - 1) - self.last_contest.at(d, k);
        let db2 = self.next_contest.at(d, k) - (d + 1);
        let da1 = self.next_contest.at(d, k) - self.last_contest.at(d, k) - 1;
        let sb = db1 * (db1 + 1) / 2 + db2 * (db2 + 1) / 2;
        let sa = da1 * (da1 + 1) / 2;
        diff -= (-self.C.at(k) * sb);
        diff += (-self.C.at(k) * sa);
        diff
    }

    fn diff_score_add(&self, d: i32, k: i32) -> i32 {
        // コンテスト追加時の差分
        let mut diff = 0;
        diff += self.S.at(d, k);
        let db1 = self.next_contest.at(d, k) - self.last_contest.at(d, k) - 1;
        let da1 = (d - 1) - self.last_contest.at(d, k);
        let da2 = self.next_contest.at(d, k) - (d + 1);
        let sb = db1 * (db1 + 1) / 2;
        let sa = da1 * (da1 + 1) / 2 + da2 * (da2 + 1) / 2;
        diff -= (-self.C.at(k) * sb);
        diff += (-self.C.at(k) * sa);
        // println!("[{}]add {} diff:{}", k, d, diff);
        diff
    }

    fn diff_score_swap(&self, k: i32, db: i32, da: i32) -> i32 {
        // コンテスト交換時の差分
        debug_assert_ne!(da, db);
        debug_assert_ne!(self.next_contest.at(db, k), da);
        debug_assert_ne!(self.last_contest.at(db, k), da);

        // db -> da に動かす場合
        let next = self.next_contest.at(db, k);
        let last = self.last_contest.at(db, k);
        let jump = (da > db && da > next) || (da < db && da < last);

        if jump {
            let mut diff = 0;
            diff += self.diff_score_remove(db, k);
            diff += self.diff_score_add(da, k);
            // println!("[{}]{}->{} next:{} last:{} jump:{} diff:{}", k, db, da, next, last, jump, diff);
            diff
        } else {
            let mut diff = 0;
            diff -= self.S.at(db, k);
            diff += self.S.at(da, k);
            let db1 = (db - 1) - last;
            let db2 = next - (db + 1);
            let da1 = (da - 1) - last;
            let da2 = next - (da + 1);
            let sb = db1 * (db1 + 1) / 2 + db2 * (db2 + 1) / 2;
            let sa = da1 * (da1 + 1) / 2 + da2 * (da2 + 1) / 2;
            diff -= (-self.C.at(k) * sb);
            diff += (-self.C.at(k) * sa);
            // println!("[{}]{}->{} next:{} last:{} jump:{} diff:{}", k, db, da, next, last, jump, diff);
            diff
        }
    }

    fn update_remove(&mut self, dc: i32, k: i32) -> () {
        // コンテスト削除のアップデート

        // commandの削除は省略
        self.score += self.diff_score_remove(dc, k);

        let mut d = dc - 1;
        while d >= 0 && self.next_contest.at(d, k) == dc {
            *self.next_contest.mt(d, k) = self.next_contest.at(dc, k);
            d -= 1;
        }

        let mut d = dc + 1;
        while d < self.D && self.last_contest.at(d, k) == dc {
            *self.last_contest.mt(d, k) = self.last_contest.at(dc, k);
            d += 1;
        }
    }

    fn update_add(&mut self, dc: i32, k: i32) -> () {
        // コンテスト追加のアップデート

        *self.command.mt(dc) = k;
        self.score += self.diff_score_add(dc, k);

        let mut d = dc - 1;
        while d >= 0 && d >= self.last_contest.at(dc, k) {
            *self.next_contest.mt(d, k) = dc;
            d -= 1;
        }

        let mut d = dc + 1;
        while d < self.D && d <= self.next_contest.at(dc, k) {
            *self.last_contest.mt(d, k) = dc;
            d += 1;
        }
    }

    fn update_swap_single(&mut self, k: i32, db: i32, da: i32) -> () {
        // コンテスト交換のアップデート（片方のコンテスト種類にのみ着目）

        let next = self.next_contest.at(db, k);
        let last = self.last_contest.at(db, k);
        let jump = (da > db && da > next) || (da < db && da < last);

        if jump {
            self.update_remove(db, k);
            self.update_add(da, k);
        } else {
            *self.command.mt(da) = k;
            self.score += self.diff_score_swap(k, db, da);
            for d in last..=next {
                if d < 0 || d >= self.D {
                    continue;
                }
                if d != next {
                    if d < da {
                        *self.next_contest.mt(d, k) = da;
                    } else {
                        *self.next_contest.mt(d, k) = next
                    }
                }
                if d != last {
                    if d > da {
                        *self.last_contest.mt(d, k) = da;
                    } else {
                        *self.last_contest.mt(d, k) = last;
                    }
                }
            }
        }
    }
}

Submission Info

Judge Result