AtCoder LibraryをGo言語に移植してみた

Aru

Gemini 3.5 FlashとAntigravity 2のチェックもかねて、AtCoder Library（ACL）をGo言語に移植してみました。これまでは、自分がこれまで作っていた別のライブラリを使っていましたが、今回はACLのC++のコードから直接変換を行ってみました。

Contents

AtCoder Libraryとは
Go言語の現在の状況
今回作成したライブラリ
- インストール方法
- 使い方
終わりに

AtCoder Libraryとは

ACL（AtCoder Library）は、競技プログラミングコンテストサイト「AtCoder」が公式に提供している、主にC++向けのアルゴリズムライブラリ集です。

公式にはC++向けだけがリリースされていますが、有志が各言語向けにライブラリを作っているので、様々な言語で利用できます。

Go言語の現在の状況

Go言語のACLとしては、以下のリポジトリが紹介されています。このリポジトリにはsccの実装などで協力はしていましたが、結局全ての関数の実装はできていない状態です。

https://github.com/monkukui/ac-library-go

遅延セグメントツリーとか畳み込みなどはまだ実装されていません。６年くらい前から実装されていましたが残念ながら完成していない状況です。

今回作成したライブラリ

今回、Antigravity 2の使い勝手チェックを兼ねてACLをGo言語に移植してみました。URLは以下になります。

https://github.com/aruaru0/ac-library-go

インストール方法

インストールおよび使い方の詳細はREADME.mdにもありますが、おすすめは以下の方法になります。

以下のコマンドでインストールします。~/go/binにパスを通していれば、acl-go-expanderというコマンドがインストールされます。これでインストールは完了です。

go install github.com/aruaru0/ac-library-go/cmd/acl-go-expander@latest

使い方

DSUを使う例です。まず、コードに以下のように書きます。

package main

import (
	"fmt"
	"github.com/aruaru0/ac-library-go/dsu"
)

func main() {
	uf := dsu.NewDSU(5)
	uf.Merge(0, 1)
	fmt.Println(uf.Same(0, 1))
}

ライブラリの呼び出しでエラーが出ると思うので、以下のコマンドを実行します

go mod init xxxx(名前はなんでもOK)
go mod tidy

これでgithub.com/aruaru0/ac-library-go/dsuが使えるようになります。あとは、通常通りビルドや実行（go runなど）が可能になります。

提出時

提出時は、以下のコマンドでライブラリをコードにマージします。

acl-go-expander -o submit.go main.go

作成されたsubmit.goは、パッケージを使わずに単体で動作するようにマージされたソースコードになります。

マージしたコードは一応確認をしてください。もしかしたらエラーになるかもです。

終わりに

Go版のACLがなかなか完成しないので、Antigravity 2の動作チェックを兼ねて作ってみました。今回、コードは斜め読みしかしてませんがなんとなくうまくいっている感じです。C++のコードのポーティングだったので、比較的エラーも少なく移植できた感じです。テストコードも移植してチェックしているのでおそらく問題ないと思いますが、これから実際に使いながらチェックしていく予定です。よろしければ活用してください。