競プロ用のライブラリを Rust で作ってみたシリーズ 〜 chmin! / chmax! マクロ編〜

競プロerのみなさん、こんにちは。

このシリーズでは、Rust で競技プログラミングをするにあたって、快適にかつ素早くコーディングをするためのライブラリを紹介していこうと思います。（不定期連載）

第1弾は chmin! / chmax! マクロを取り上げます。
（ ch は change の略です。chmod とかと同じノリです。）

TL;DR

今回作った chmin! chmax! マクロは以下のようなものです。（折りたたみ）

マクロを見る場合はこちらをクリック

macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}

chmin / chmax とは

まずはじめに、競プロの文脈において chmin や chmax がどのような使われ方をするものなのかをまとめます。
競プロ界の伝道師（と勝手に僕が思っている） @drken さんの以下のエントリ内で、C++ における chmin chmax が紹介されています。

• 動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

こちらのエントリを読むとよく分かりますが、競プロでよく問われる「何かを最大化／最小化しなさい」というような問題を解くにあたって、

「今まで出てきた値の中で最小のもの a と、今見ている値 now を比較して、もし now のほうが小さかったら a を更新する」

みたいな処理をすることがしばしばあるかと思います。
たとえば一番単純な例だと、ある数列の中の最小の値を求めたいときに、とっても素朴な書き方をすると以下のようになると思います。（あまりにも Rust 的ではない書き方ですが、そこは目をつぶってください）

let list: Vec<i32> = vec![5, 4, 10, 23, 3, 1, 42];
let mut a = std::i32::MAX; // 今まで出てきた値の中で最小のものを保存しておく変数

for now in list {
    if now < a {
        a = now;
    }
}

println!("{}", a); // list の中の最小値である 1 が出力される

このような処理をするときに、chmin! を使うと以下のように書けます。（for ループ部分のみ抽出）

for now in list {
    chmin!(a, now);
}

a と now の大小関係を判定して、その後の a の値の更新までやってくれる というイメージです。

上のような単純な例だとあまり得をした気がしないですが、DP テーブルの更新のように、添字がたくさんあってタイピングするのが大変なときなどにはかなり重宝します。

例えば、すべての2頂点の間での最短経路を求めるアルゴリズムとして有名な ワーシャル–フロイド法 を、上記の素朴なやり方で書くと以下のようになります。

for k in 0..N {
    for i in 0..N {
        for j in 0..N {
            // 書くのが大変！！
            if dist[i][k] + dist[k][j] < dist[i][j] {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

（かなりわざとらしく大変になるように書いてはいますが）なんか添字がたくさんあってブラケット記号 [] がゲシュタルト崩壊しそうになりますしタイピングも大変です。

これが chmin! を使えば、for の中身に関しては次の1行で済みます。小指に優しい！

chmin!(dist[i][j], dist[i][k] + dist[k][j]);

chmin! chmax! の有用性がお分かりいただけたかと思います。

chmin! chmax! を作っていく

有用性が分かったところで、早速マクロの作成に入っていきます。

………ここまで「マクロで作る」ということを前提としてきてしまいましたが、そもそもマクロで作るのはなぜ？関数じゃダメなの？という疑問をもった方もいらっしゃると思います。
マクロで作った理由についてや、マクロの詳しい入出力の仕様などをこちらに載せてしまうと記事が長くなってしまうかと思い、これらは appendix としてブログのほうにまとめることとしました。
よろしければブログのほうもご覧いただければと思います。

• maguro.dev 競プロ用のライブラリを Rust で作ってみたシリーズ 〜 chmin! / chmax! マクロ編〜 Appendix

仕様を決める

さて、マクロを書いていくために、仕様を決めていきます。
なお、以下では chmin! を作成していくことを考えます。 chmax! もほとんど同じ書き方になるためです。

仕様を検討する

まず仕様、というか存在意義そのものですが、chmin!(a, b) と書くことで

【仕様1】 もし $a \gt b$ ならば、$a$ に $b$ を代入する。そうでないなら、何もしない

というような仕様は必要になってきます。

それに加えて、上でリンクを貼った @drken さんによる chmin chmax 関数の実装では、
実際に更新が行われたら true を返し、行われなかったら false を返す
というような実装となっています。このようにすることで、DP の経路を復元したいときに役立つようです。
参考: いろんな人のテンプレートを観察 - memo

この仕様を踏襲したいところです。以下の仕様も加えましょう。

【仕様2】 更新が行われたら true を、行われなかったら false を返す

また、せっかくマクロを使うので、少し欲張りな実装にしてみたいところです。つまり、比較対象の値をいくつでも書けるようにしたいです。例えば、chmin!(a, x, y, z) と書いたら
$a$ が $a, x, y, z$ の最小値に置き換わる
ようにしてみたら、役立つ場面がきっとありそうです。最後の仕様としてこれを加えることにしてみます。

【仕様3】 比較対象の値をいくつでも取れるようにする

決まった仕様

3つの仕様が固まりました。

1. もし $a \gt b$ ならば、$a$ に $b$ を代入する。そうでないなら、何もしない
2. 更新が行われたら true を、行われなかったら false を返す
3. 比較対象の値をいくつでも取れるようにする

マクロを書く

仕様が決まったので、マクロを作っていきます。仕様をぐっと睨むと、まず可変長引数に対応したバージョンの std::cmp::min を用意すると良さそうな気がしてくるので、こちらを先に作ってみましょう。

min!マクロ

macro_rules! min {
    // 引数が 1 個だけの場合は、そのまま返す
    ($a:expr $(,)*) => {{
        $a
    }};
    // 引数が 2 個の場合は、std::cmp::minを使用して小さい方を返す
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    // 引数が 3 個以上ある場合は、再帰的に min! マクロを呼び出す
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+)) // 第2引数以降の部分に対して再帰呼び出し
    }};
}

このような感じで、引数が1個、2個、3個以上、という3つのパターンを用意します。3個以上のパターンの場合には再帰的にマクロを呼び出すことで、可変長引数に対する最小値を求めることができます。
chmin! マクロを作るための補助マクロとして作成しましたが、これ単品でも使える場面はありそうなので、手元の競プロテンプレートに加えてもいいかもしれません。

さて、min! マクロができたので、これを使って chmin! を作ります。以下のように、min! を使うことでシンプルに書くことができます。

chmin!マクロ

macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        // 第2引数以降の部分に関して、min! を使用して最小値を求める
        let cmp_min = min!($($cmps),+);

        // それが第1引数より小さかったら、更新して true を返す
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            // 更新が不要なので、false を返す
            false
        }
    }};
}

完成したマクロ

というわけで、3つの仕様を満たした chmin! が無事に完成しました。
chmax! も同じように作成し、できあがった4つのマクロを掲載します。

マクロ完成形

macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}

最後に

Rust 以外の言語でよく使われる便利関数 chmin chmax を、マクロを使うことで Rust でも再現することができました。
マクロは普通の Rust とは見た目が違って異質な感じがしますが、自分でいくつか書いてみるとだんだんわかるようになってきて、他人が書いたマクロでも読めるようになってくる感じがして楽しいです。
みなさんもマクロを使いこなして快適な競技プログラミングライフを送りましょう👍
今後も自分のライブラリを整備したらこのような形で投稿できたらと思っていますので、よろしくお願いします。

参考リンク

• 動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita
  • chmin chmax の使いどころがたくさんまとまっています
• いろんな人のテンプレートを観察 - memo
  • C++ での競プロテンプレあるあるがまとめられています。chmin chmax も紹介されています
• maguro.dev 競プロ用のライブラリを Rust で作ってみたシリーズ 〜 chmin! / chmax! マクロ編〜 Appendix
  • 本エントリの Appendix として、なぜ関数ではなくマクロにしたのかや、ユニットテストの内容などを載せています
• maguro.dev - 競技プログラミングでの使い勝手を考えたオレオレデバッグマクロを作りました
  • 競プロライブラリ作成シリーズ第0弾（？）で、ローカルで実行したときにだけ動くデバッグ用のマクロを作ったので、その紹介をしています