この記事は アドベントカレンダー2025 6日目の記事です。
はじめに
24Bの ＠zoi_dayo です。普段はたまに競プロをしたりしています。
少し前にICPC Taichung Regionalに出てきました。このときにチームのライブラリを作ってみたので紹介します。
zoi_dayo
ところで明日にICPC Yokohama Regionalがあるらしいです。応援!!
ライブラリって何
競プロではいろいろ典型的なテクニックが要求されます。特にデータ構造などであれば、一度汎用的なコードを作れば、次からはそれを使い回すだけでよいことが多いです。これをいちいち書いていると大変なのでコード片をメモしておこうということです。
AtCoderに参加している人なら、 ac-library をご存知かもしれません。AtCoderのC++環境でデフォルトで使用可能になっているAtCoder公式ライブラリです。
他にも Nyaan's Library 、 Luzhiled's Library なども有名なんじゃないかと思います。これらは verification-helper あたりのツールを利用して作られていることが多いですね。
ところが、ICPC用のライブラリとなるとすこし要件が変わってきます。ICPCでは、(大会によりルールが異なるので一概には言えませんが) 「A4片面 25ページ以下の紙ライブラリのみ持ち込み可能」のようなルールが定められていることが多いです。すなわち、通常のコンテスト用ライブラリとは異なり、
- 特定のページ数に収めないといけない
- boost、ac-libraryなどは使えない
- 書き写さないといけないのであまり長いコードは書きたくない
- 逆に、(バグがないなら) 内部の可読性とかは一旦無視しても良い
- 目次のページがあったほうがよい
- PDF化の機能があったほうがよい
- 逆に、Webページとして公開する機能はなくても良い
などが求められます。
ので、ICPCに出場するチームは、多くの場合は Speed Star の ICPC Notebook や KACTL を利用します。というかぶっちゃけこれらが最強です。あれ... (記事終了)
つくってみよう!
Speed StarのライブラリやKACTLを使ってもよいのですが、これらのライブラリには知らないデータ構造とかが大量に乗っており、またもう少し日本語のドキュメントを載せておきたいと感じたので、チームのライブラリを作ってみたいねという話になりました。
出来たものがこれです:
ICPC-Tsukuyom1
ライブラリのコードは、基本的にメンバーが持っていたもの + kactlやNyaan's Librayを参考に編集したものを集めています。ので、網羅性としては各種ライブラリの下位互換という感じです。
その分ページ数に余裕が出るので、使い方、参考情報などのドキュメントは増やしています。
こだわりポイント
ここからはこだわりポイントの紹介です。
PDF化
印刷前提のライブラリなので印刷できないといけません。この目的なら普通は ICPC Notebook を利用するとよいです。なぜ使わなかったのか? わかりません...
要件を整理します。
- (traPではMarkdownが公用語なので) ドキュメント部分は Markdown、またはそれに近い書き心地のもので記述したいです。
- レイアウト全部TeX打ちは嫌です。
- HTML/CSSゴリ押しも嫌です。
- でもレイアウトはそれなりに自由度がほしいです。
- 数式とコードをきれいに表示したいです。
- コードはドキュメントとは別ファイルにしたいです。
#includeでVerifyしたいため
- ドキュメントは各cppファイルくらいの単位で作り、最終的にそれらがすべてまとまったPDFが出力されるようにしたいです。
- ドキュメント→PDF変換は自動化したいです。
まず候補に上がるのが Markdown → PDF 系のツールです。Markdownは (Webの各所で使われていることから分かる通り) 簡単にHTMLに変換することが出来ます。というかHTMLをドキュメントに特化させた省略記法です。
HTMLまで変換してしまえば、あとはヘッドレスなブラウザを起動し、ブラウザの印刷機能を利用してPDFに変換することができます。ここまでをやってくれるツールはWebの各所に落ちています。
これは便利なのですが、昔使ったときに改ページのところで文字が切れてしまったような記憶があるのと、段組のレイアウトを作るためににはCSSを頑張らないといけないこと、またmdファイル内に外部のcppファイルを埋め込めるかわからないということで一旦別の方法を考えてみることにしました。(あとヘッドレスブラウザが重いのでできればCIで動かしたくない)
ここで選んだのがTypstです。レポートなどに使っている方も多いと思うのですが、簡易版TeXのような存在です。(TeXほどではないですが) 柔軟なレイアウトが可能で、md(HTML)とは異なり最初から印刷物の作成を想定したツールなので都合が良いです。
Typstには #import や #include という機能があり、他のTypstファイルの内容を埋め込むことが出来ます。また、 #outline() で目次も作れるし、codelst パッケージ の #sourcefile(filename) を利用すれば外部ファイルを読み込んでシンタックスハイライト付きで表示することも出来ます。最高ですね。
GitHub Actionsを利用して、mainブランチまたはPRに変更が入った時にPDFをビルドしてArtifactとして出力するようにしています。フォントは Fira Code + Noto Sans CJK JP です。
ICPC-Tsukuyom1ただ欠点もあって、TypstよりTeXのほうが歴史があるため、適当にGitHub Copilotに任せているとTypstファイルにTeXを書いてコンパイルエラーを出してしまいます。ちゃんとやりましょう。
Verify
前述の通り、C++のファイルを分離しているので、 #include を利用してコードを書くことができます。CIでの自動テストも走らせたいですね。
こういうときは基本 verification-helper を利用するとよいです。が、ドキュメント生成機能が2種類できるのはあまりきれいじゃないと思ったこともあり、せっかくなので自分で作ってみました。
verifyフォルダ以下に //@yosupo {問題id} または //@yukicoder {問題id} から始まるファイルを配置することで自動的にテストが走ります。Libray Checkerについては 問題が公開されている ので、ここにあるコードを用いてテストケース生成とジャッジを行いました。yukicoderについては online-judge-tools を利用しています。
GitHub ActionsのMatrix機能を利用して複数の問題のテストが同時に走るようにしています。これにより、Verify対象が増えてもそれなりの時間で完了することができます。
実行時は (Library Checkerの場合は生成時もですが) ulimit -s unlimited を忘れないようにしてください。これによりスタックサイズ上限をなくすことができます。なお、DOMJudgeでも同様のスタックサイズ上限拡張が行われているため、本番だとエラーになるということはないはずです。
DOMjudgeドキュメント系
gdb の使い方や乱数、タイマー、bit演算 ( O(3n) のforとか) 、組み合わせの公式などドキュメントはまあまあ書いてます。ただタイマーを使う問題がICPCに出るかと言われるとかなり出ない気がしています。
作ってみて
自分たちの能力で使えて、かつ実装がめちゃくちゃ重い訳では無い、というものに関してはだいたい網羅出来たと思います。Verifyのカバレッジがかなり低いところは心配ですが... (適切な問題を見つけるのが難しい)
ライブラリ作成にTypstを利用している例はあまり見かけないのですが、かなり使いやすかったので印刷目的であればかなりおすすめです。Chromium系よりもバイナリサイズが小さいのでGitHub Actionsでの動作も軽いですし、手元での出力・プレビューも簡単です。
