Rustでヒューリスティックコンテストを解いてみる

Rustのお勉強として、RustにIntroduction to Heuristics Contestの解答を移植しました。

atcoder.jp

気になるポイント

私は競プロではC#を使っているのですが、だいぶ書き方が異なる部分があり戸惑っています。 C#だとこう書く、というのが煩雑な書き方になったり、不可能だったりするのでそこの見極めができないと厳しい。。

以下、自分なりに工夫した点ですが、より良い方法があれば教えて頂けると助かります。

ローカル環境とAtCoder環境の切り替え

ローカルでは便利クレートを使い、AtCoderではそれらをコンパイルしない、としたいです。
フィーチャーフラグを使うことで対応しました。

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

struct Logger {}

#[cfg(feature = "local")]
impl Logger { 
    // loggingの記述
}

#[cfg(not(feature = "local"))]
impl Logger {
    // 何もしないメソッドの実装
}

入力

proconioに頼るのも良いのですが、今回はローカルではファイルからの読み込みに切り替えたいため、普通に書きました。 マクロを書くとだいぶ扱いやすくなります。

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

let mut D: i32;
let mut C: Vec<i32>;
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}

Vecとusize

Vecのインデックス参照を行うときにi32型は許してくれず、usize型でないとエラーになります。
D[i as usize][j as usize][(k + 1) as usize] は可読性が厳しいと思ったので、トレイトを作って対処しましたが、もう一声すっきり書きたいなぁという感じです。

trait IndexAt<T> {
    fn at(&self, i: i32) -> T;
    fn mt(&mut self, i: 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]
    }
}

// 2次元配列に対応する記述は省略

atメソッドで値を取得、mtメソッドで可変参照を取得なのですが、できればポインタは自動で外したい・・

// 1次元配列に対応するVecを参照する
if self.command.at(d) == k {
    last = d;
}     

// 2次元配列に対応するVecを更新する
*last_contest.mt(d, k) = last;

時間測定

wataさんのコードが参考になります。
スタティックライフタイムで開始時間を保持しているのですが、 関数内で定義した変数が関数を抜けても保持され続けるのはなかなか面白いですね。

// https://atcoder.jp/contests/intro-heuristics/submissions/14855120 より
pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    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 STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

グローバルな静的クラス

Rustだと、グローバルな静的クラスに相当するものが作りにくいです。 lazy_staticを使う方法など試しましたが、どうしても煩雑になってしましました。 結局、Config構造体やInput構造体の参照をどんどん渡していく方法としています。

Enum

Enumが強力だということで、とりうる行動（今回ではコンテストの交換、コンテストの変更）をEnum型にしてみました。 EnumのVariantを関数の引数にはできないため、構造体を作る必要があります。
また、パターンマッチでムーブしてしまうので、Copyトレイトを実装しなくてはいけません。
Enumを使わない場合に比べて、ちょっと扱いやすくなったような、そうでもないような。

#[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,
}

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) {
    match action {
        Action::Swap { action } => state.update_swap(action),
        Action::Change { action } => state.update_change(action),
    }
}

参考文献

Rustを学ぶにあたって、以下を参考にさせていただきました。

Rustの日本語ドキュメント、プログラミング言語Rust日本語版
https://doc.rust-jp.rs/
https://doc.rust-jp.rs/book-ja/

実践Rustプログラミング入門
www.amazon.co.jp

序盤の章で言語の特長や抑えておくべき概念、文法をざっくり説明してくれるのが分かりやすかったです。

実践Rust入門[言語仕様から開発手法まで]
https://www.amazon.co.jp/dp/4297105594

AtCoderコンテストにRustで参加するためのガイドブック
https://doc.rust-jp.rs/atcoder-rust-resources/