AtCoder 言語アップデートクレート個人的感想

2023-08-06 の新ジャッジテストコンテスト -Algorithm- 以降から AtCoder で使える Rust のバージョンが 1.70.0 になり、以下のクレートが使えるようになりました。それらを主観で使えそうとか雑にコメントしていく記事です。

ac-library-rs = "0.1.1"
once_cell = "1.18.0"
static_assertions = "1.1.0"
varisat = "0.2.2"
memoise = "0.3.2"
argio = "0.2.0"
bitvec = "1.0.1"
counter = "0.5.7"
hashbag = "0.1.11"
pathfinding = "4.3.0"
recur-fn = "2.2.0"
indexing = "0.4.1"
amplify = "3.14.2"
amplify_derive = "2.11.3"
amplify_num = "0.4.1"
easy-ext = "1.0.1"
multimap = "0.9.0"
btreemultimap = "0.1.1"
bstr = "1.6.0"
az = "1.2.1"
glidesort = "0.1.2"
tap = "1.0.1"
omniswap = "0.1.0"
multiversion = "0.7.2"
num = "0.4.1"
num-bigint = "0.4.3"
num-complex = "0.4.3"
num-integer = "0.1.45"
num-iter = "0.1.43"
num-rational = "0.4.1"
num-traits = "0.2.15"
num-derive = "0.4.0"
ndarray = "0.15.6"
nalgebra = "0.32.3"
alga = "0.9.3"
libm = "0.2.7"
rand = "0.8.5"
getrandom = "0.2.10"
rand_chacha = "0.3.1"
rand_core = "0.6.4"
rand_hc = "0.3.2"
rand_pcg = "0.3.1"
rand_distr = "0.4.3"
petgraph = "0.6.3"
indexmap = "2.0.0"
regex = "1.9.1"
lazy_static = "1.4.0"
ordered-float = "3.7.0"
ascii = "1.1.0"
permutohedron = "0.2.4"
superslice = "1.0.0"
itertools = "0.11.0"
itertools-num = "0.1.3"
maplit = "1.0.2"
either = "1.8.1"
im-rc = "15.1.0"
fixedbitset = "0.4.2"
bitset-fixed = "0.1.0"
proconio = "0.4.5"
text_io = "0.1.12"
rustc-hash = "1.1.0"
smallvec = "1.11.0"

ac-library-rs

ACL の Rust版ですね。大体これのドキュメントを読めば分かるはず

use ac_library::Dsu;

fn main() {
    Dsu::new(10);
}

とかやれば使える

once_cell

１度しか初期化できない型を提供している。

static_assertions

定数や型に関するアサーションを提供している。コンパイル時にチェックされるらしい。

varisat

SAT ソルバー。なんで入ってるんだろう…？（2-SAT とか書くの楽なのかな？）。

この辺読めば使えそう

use varisat::{ExtendFormula, Lit, Solver, CnfFormula};

fn main() {
    let mut formula = CnfFormula::new();
    let (a, b, c) = (Lit::from_dimacs(1), Lit::from_dimacs(2), Lit::from_dimacs(3));

    formula.add_clause(&[a, b, c]);
    formula.add_clause(&[!a, !b]);
    formula.add_clause(&[!b, !c]);
    formula.add_clause(&[!a, !c]);

    let mut solver = Solver::new();
    solver.add_formula(&formula);

    let result = solver.solve();
    assert_eq!(result.unwrap(), true);

    let model = solver.model().unwrap();
    eprintln!("{:?}", model);
    // [-1, 2, -3]
}

もしかしたら文字列で渡すほうが用意しやすいかも？

let dimacs_cnf = b"1 2 3 0\n-1 -2 0\n-2 -3 0\n";

solver.add_dimacs_cnf(&dimacs_cnf[..]).expect("parse error");

memoise

関数をメモ化してくれる

use memoise::memoise;
#
#[memoise(n <= 100)]
fn fib(n: i64) -> i64 {
    if n == 0 || n == 1 {
        return n;
    }
    fib(n - 1) + fib(n - 2)
}

memoise と書いたら Vec、 memoise_map と書いたら BtreeMap でメモ化してくれるみたい。

ABC314 E をこれで解いてみた（ソースコード）。使い勝手良さそう。

argio

関数の入出力を stdio に変換するマクロらしい。内側では proconio を使っているから proconioと同じ感じで書けるらしい。たまに嬉しそう？

#[argio]
fn main(n: i32) -> i32 {
    n * 2
}

bitvec

C++ にもある bitset みたいに使えるやつっぽい。（これ系いつも使い方わかりません）。こんな感じで使えるっぽい？

fn main() {
    let mut bits = bitvec![usize, Msb0; 0; 20];
    bits.set(0, true);
    
    for c in [1 , 6, 7, 10] {
        let mut shift = bits.clone();
        shift.shift_right(c);
        bits |= shift;
    }

    println!("{:?}", bits);
    assert_eq!(bits[13], true);
}

counter

Python の counter を参考にしているらしい。 most_common とかがあるのは便利かも？

use counter::Counter;

fn main() {
    let v = vec![1, 4, 2, 4, 3, 4, 4];
    let counts = v.iter().collect::<Counter<_>>();
    eprintln!("{:?}", counts);
    assert_eq!(counts[&1], 1);
}

hashbag

unordered_multiset。contains で数がとれるらしい。

pathfinding

グラフアルゴリズムが入っているらしい。

A*
BFS
Brent
DFS
Dijkstra
Edmonds Karp
Floyd
Fringe
IDA*
IDDFS
strongly connected components
topological sorting
Yen
connected components
Kruskal
Kuhn-Munkres

recur-fn

ラムダ再帰ができるようになるやっぽい

use recur_fn::{recur_fn, RecurFn};
fn main() {

    let fib = recur_fn(|fib, n: i32| {
        if n <= 1 {
            n
        } else {
            fib(n - 1) + fib(n - 2)
        }
    });

    println!("{}", fib.call(10));
}

indexing

unchecked な indexing ができるらしい。ライブラリ作りには嬉しそう

amplify

マクロとか追加するやつ。

こういうことができるらしい。（BtreeMap の宣言）

#[macro_use]
extern crate amplify;

let map = bmap! {
    s!("key") => 5,
    s!("other_key") => 10
};

easy_ext

extension-trait-conventions をもっと簡単に記述するためのマクロ

multimap

HashMap を使った multimap

btreemultimap

BtreeMap を使った multimap

bstr

バイト文字列のライブラリ。

az

型キャストした時にチェックしてくれたりする。(-1).wrapping_as::<u32>() とかすると 1u32.wrapping_neg() が得られる。

glidesort

安定ソート。早いらしい。

tap

tap とか pipe とかを間に挟み込める。tap はデバッグとかに使えて、 pipe は変換とか挟み込める。消し忘れそう…。

use tap::Tap;

fn main() {

    let n = 13;
    let odd_sum = (0..n).filter(|&x| x % 2 == 1)
        .tap(|x| println!("odd: {:?}", x))
        .sum::<usize>();

    println!("{}", odd_sum);
}

omniswap

参照が重複して std::mem::swap できないやつも swap できるようにするマクロ。

fn main() {
    let mut a = vec![vec![1, 2, 3], vec![4, 5, 6]];
    // std::mem::swap(&mut a[0][1], &mut a[1][3]); // これはダメ
    omniswap::swap!(&mut a[0][1], &mut a[1][3]);
}

multiversion

CPUによって関数の実装を変えたりできるやつ。

num

整数色々。num-bigint、 num-complex、num-integer とか色々ある。整数範囲の sqrt とか便利。

ndarray

行列ライブラリ

nalgebra

行列ライブラリ

alga

代数系トレイト。Monoid とか入ってる

libm

libm の Rust 実装。 f32, f64 の便利関数が色々

rand

乱数関連の色々

getrandom

OS の乱数生成器のインターフェース

petgraph

グラフライブラリ。前のバージョンでも入っていた。

indexmap

なんか色々機能のある HashMap と HashSet

regex

正規表現。前のバージョンでも入っていた。

lazy_static

遅延評価のマクロ。前のバージョンでも入っていた。

ordered-float

Float のラッパー。前のバージョンから入っていたらしい。Float をソートするときに楽できる。

let mut v = [OrderedFloat(NAN), OrderedFloat(2.0), OrderedFloat(1.0)];
v.sort();
assert_eq!(v, [OrderedFloat(1.0), OrderedFloat(2.0), OrderedFloat(NAN)]);

ascii

ASCII文字列・文字を扱うやつ。前のバージョンでも入っていた。

permutohedron

next_permutation とかを提供している。前のバージョンでも入っていた。

superslice

超便利なやつ。 lower_bound とかを提供している。前のバージョンでも入っていた。

use superslice::*;
 
let b = [1, 3];

assert_eq!(b.lower_bound(&1), 0);
assert_eq!(b.upper_bound(&1), 1);
assert_eq!(b.equal_range(&3), 1..2);

itertools

これも超便利。 iter に対して色々できる。前のバージョンでも入っていた。

maplit

HashMap とかがマクロで定義できるやつ。amplify と近いかも

im-rc

永続データ構造が使える。色々なデータ構造が入ってる。

fixedbitset

bitset

bitset-fixed

bitset

proconio

競プロの IO を楽にするやつ。

rustc-hash

高速で非暗号なハッシュ