Rustで小さな競プロ用ライブラリを作ってみた話

学生の頃のRustと競プロ

Rustに触れ始めたのは、まだ競プロを始める前でした。actix-webを用いたバックエンドのサーバ構築、clapを用いた簡単なCLIツール開発、wasm-packを使ったRustからWebAssemblyへのコンパイルなどなど様々な範囲に手を出しながら、Rustの所有権、ジェネリクス、トレイトなどについて理解を深めていました。

そのうちアルゴリズムに興味をもって競プロを少しずつ始めるようになりました。最初はPythonで解いていたのですが、「どうせなら普段触っているRustで提出してみたい！」と考えるようになり、途中からはほとんどRustで書くようになりました。制約の厳しい問題をRustで解いていると、アルゴリズムそのものに加えて、所有権やライフタイム、標準ライブラリの中身といった部分も試されているような感覚があるので、楽しく学ぶことができていました。
(Pythonを触っていた身だと文字列周りが難しく、エラーが出てしまうことも少なくありませんでした。)

とはいえ、コンテスト中はとにかく時間内にACを取りにいくことが優先なので、場当たり的にコードを書くことも多くなります。とりあえず正常に動くコードが書けるのであれば細かい設計の話をしている暇はないわけです。一方で、いつもお世話になっているライブラリを自分で作ることに憧れがあったので、いい機会だと思いライブラリの形に整えてみようと思いました。

RustCompetitiveを作ったときの話

そういう思いが沸き上がったタイミングで、勉強がてら作ったのが RustCompetitiveの始まりです。卒業前の2024年6月ごろ、競プロで印象に残っていたものをいくつか選んで、「アルゴリズムとして何をしているのか」「Rustとしてどう書くことができるか」を自分なりに整理し直してみることにしました。

対象にしたのは、大きく分けると「整数」「文字列」「行列」という三つの分野です。どれもコンテスト中に何度も目にするテーマで、アルゴリズムの教科書にも必ず出てくるような題材ですが、Rustで書こうとするとジェネリクスやトレイトの概念がついてきます。その組み合わせを一度落ち着いて考えてみたかった、というのが、あのときの正直な動機でした。

具体的な断片たち

整数の処理：平方根とべき乗とmod

まずまとめたのは、整数まわりの処理です。

わざわざ剰余をとる処理をせずとも、内部で都度剰余をとってくれるModInt、整数Nの平方根の整数部分を二分探索で求める関数、整数N、Mに対してN^Mを繰り返し二乗法で計算する関数、また、その計算した数をPで割った余りを効率よく計算する関数を入れました。

アルゴリズム自体はどれも教科書に載っているような定番ですが、いざ実装してみると、

• どこまでの機能をderiveするか
• 最低限どのトレイとを実装すれば使えるか
• オーバーフローすることを考えてResultで返すのか、競プロで手軽に扱うことを考えてオーバーフローしない前提の実装にするか
• 負の数でも扱えるようにするか

などなどを細かく考える必要が出てきました。最初は「せっかくだからジェネリクスで書いてみよう」と試してみたものの、Copyや演算用のトレイトをどこまで要求するかを考え始めると、一気に複雑になり、自由度が下がってしまいました。

最終的には、「競プロで使う範囲でよく使うusizeに振り切ってしまおう」と割り切り、オーバーフローも「ジャッジが与える入力の範囲に任せる」方針にしました。アルゴリズムの計算量や境界条件を自身の問題文を読み解く力と相談しながら、折り合いをつけるかを決めていく作業は、自身の実力に向き合ういい機会でした。

文字列の処理：回文とランレングス

次に手をつけたのが文字列です。文字列が回文かどうかを調べる関数、回文にするために最低限変えるべき文字数を数える関数、そしてランレングス圧縮を行う関数を入れました。

これらはアルゴリズムとしては素直で、両端からポインタを動かしたり、同じ文字が続く区間の長さを数えたりするだけです。ただRustで書くとなると、&strとStringをどう分けるか、そもそもその2つの違いは何か、chars()ベースで扱うのかbytes()で扱うのか、日本語やマルチバイト文字を前提にするのか、といった基礎の部分も含めた前提をはっきりさせないと、すぐにコードが不安定になります。

当時の自分は、「競プロの文脈においては基本US-ASCIIで表現できる文字しか出てこない」という割り切りを置いたうえで、関数のインターフェースはできるだけ&strとusizeだけで済むようにそろえていました。そうしておくと、呼び出し側で余計なコピーを書かずに済みますし、「この関数は文字列のどこまでを責任範囲にするのか」が自分でも見えやすくなります。回文やランレングスといった基本的な題材を通じて、文字列まわりの仕様をもう一度地道に確認していた時期だったなと、いま振り返ると思います。

行列の処理：動的計画法と漸化式

最後に行列です。2次元配列を行列とみなし、行列累乗を計算する小さなものです。状態数が少ない動的計画法や、フィボナッチ数列のような線形漸化式を高速に計算したいときに、行列でまとめてしまう手法は競プロでも登場します。

ここでは、「行列をどういう型で持つか」「所有権をどちらに置くか」をかなり試行錯誤していました。Vec<Vec<usize>>にして柔軟性を優先するか、固定長配列でパフォーマンスを取りにいくか、積のたびに新しい行列を返すのか、、などです。いくつか書き直してみた結果、「ライブラリ側はシンプルにVec<Vec<usize>>を受けて新しい行列を返す形にしておき、最適化が必要になったときは問題ごとに書き換える」という落としどころに落ち着きました。

行列に落とし込む過程で、元の漸化式の構造も前より整理して考えられるようになり、「アルゴリズムの理解」と「Rustの書き方」が同時に進んでいく感覚があったのを覚えています。

言語のアップデートと、コードの居場所

RustCompetitiveを書いてからの1年半ほどのあいだに、Rust本体も少しずつ進化しました。前半に記述した整数平方根については、あとから isqrt というメソッドが標準ライブラリに入ったため、使う機会はなくなりそうです。
一方で、mod付きべき乗や回文判定、ランレングス圧縮、行列累乗のような処理は、2025年現在も標準ライブラリには直接の対応があるわけではないようなので、自前の実装をそのまま使う予定です。

全部を追いかけているわけではありませんが、「書いたときには必要だった関数が、数年後には標準 API の一部になっているかもしれない」「逆に、いつまでも自前で持っておく方が都合のよい処理もある」という距離感を、小さなライブラリを通じて体験できたのは面白い経験でした。

今、読み返して思うこと

当時は「便利そうな処理を関数に切り出しておこう」くらいの感覚でRustCompetitiveを作っていました。改めて読み返してみると、一つひとつの関数について、どの型を選ぶか、どこまでを責任範囲にするか、エラー処理をどこで諦めるか、といったことをかなり真面目に悩んでいた形跡が残っています。アルゴリズムの中身と言語仕様の両方を、学生の頃の自分なりにまとめていたんだな、という気がします。一方で、開発経験が浅かったころの独特な関数の命名やモジュール分割のやり方などは今見るとまだまだだなあと思います。

競プロの問題を解いている最中は、どうしても「制限時間内にACできるか」に意識が向きますが、一度コンテストから離れて自分用のライブラリを作ってみると、別の種類の学びが得られます。「この型で本当によいか」「この関数はどの範囲まで面倒を見るべきか」「使うアルゴリズムを汎用的な形で実装できるか」といった問いに向き合う時間が増えて、その過程で所有権やライフタイム、trait やジェネリクスの輪郭も、少しずつはっきりしていきました。

おわりに

なんとなくで作り始めたライブラリでしたが、作り始めるとその言語特有の仕様や書き方、エコシステムにふんだんに触れ、実装することで言語仕様を深く理解するいい機会となりました。

また、いまの自分から見ると直したくなるところもたくさんありますが、そのギャップごと含めて振り返る対象としてちょうどいいサイズの過去の成果物になっている気がします。

この記事を読んでいる方の中にも、昔の競プロ用テンプレートや個人用スニペットがどこかに眠っている、という人がいるかもしれません。もし時間があれば、一度それらを掘り起こして、今の自分の視点で少しだけ整え直してみるのも面白いと思います。あのとき何を大事にしてコードを書いていたのかが見えてきて、言語との距離感や、自分のものづくりの癖が、少しだけ輪郭を持ってくるかもしれません。