競プロ用ライブラリを作る Advent Calendar 2024の25日目です.
何するの?
似ているトレイトがバラバラに定義されてたのを一か所にまとめたり, ドキュメントを拡充したりします.
util.rsにまとめる
例えば群とモノイドが全然違うところで定義されてたりするのでこれをまとめたりします.
代数的なトレイトは以下で利用されていたので, 要件ごとにトレイトを作成してまとめました.
- WeightedUnionFind - 群
- SegmentTree - モノイド
- SparseTable - 冪等なモノイド
- BinaryIndexedTree - アーベル群
- LazySegmentTree - 遅延伝搬可能なモノイド
- PersistentSegmentTree - モノイド
- MasterTree - なんかいろいろ
LazySegmentTreeの遅延伝搬する作用素や, MasterTreeのトレイトは用途が限定的で一般化するメリットが少ないので, そのままにしておきます (MasterTreeのトレイトは専用に各演算を定義し直しているので, 最適化すると利便性が下がってしまいます)
また, 「最小値が存在する (RadixHeap)」や,「加法の単位元が存在する (Dijkstra)」などの条件も一般的であるため, 共通化しておきます. ついでに「乗法単位元が存在する」「最大値が存在する」なども作っておきましょう
コメントを書く
のドキュメントを書き忘れていたので, 書きました.
clippyに怒られる
cargo clippyするとめちゃめちゃ怒られました. (39箇所)
-
lenがあるならis_emptyも実装しろ -
Defaultを実装しろ - 無駄なライフタイム注釈を省略しろ
などなど...
修正した結果, 冤罪が1件だけあり, ModIntの
impl<const N: u32> Div for ModInt<N> {
type Output = Self;
fn div(self, rhs: Self) -> Self {
self.mul_pow(rhs, Self::PHI - 1)
}
}
というソースコードで「割り算なのに引き算の記号あるんだけどおかしいんじゃねぇの」とのことです. もちろんオイラーの定理を変形するとこうなので間違ってません.
まとめ
完走した感想ですが, めっちゃきつかったです. (学校のレポートもあるのでなんかもうすごかったです)