メルカリ summerintern-gophers-2020 に参加して,競プロ用のコード生成ツールを作った話
メルカリ主催の「summerintern-gophers-2020」に参加してきました!
概要はこちら
前半2日間は、Goの静的解析に関する講義やプログラミング言語Go完全入門の資料で参加者が興味を持つ領域を中心とした講義をWorkshopを交えながら実施。後半3日間では、静的解析ツールまたはその周辺ツールの開発に取り組んでいただきます。開発に取り組む期間は、メルカリ・メルペイのエンジニアがメンターとしてサポートします。
前半に行われた講義資料は,なんと公開されています(びっくりですね). 14 章の「静的解析」を扱いました. engineering.mercari.com
何を開発したか
競技プログラミング用のコード生成ツールを開発して,公開してあります.
詳しい使い方は,GitHub の README.md
をお読みください.
gpcg(go-procon-code-generator)
何ができるか
競技プログラミングでは,単一のファイルで記述されたソースコードを提出する必要があります.
一方で,複雑なアルゴリズムやデータ構造は事前に実装しておいて,コンテスト中はライブラリとして使用したいです.
gpcg
を用いると,複数ファイルにまたがるコード群を一つにまとめて,提出用のコードを生成してくれます!
AtCoder Beginner Contest D 問題 を題材に具体例を紹介します.
この問題は,オブジェクトのグループ分けを管理するデータ構造を使えば解くことができます.
有名なデータ構造として,UnionFind
が挙げられますが,コンテスト中に UnionFind
を一から実装すると タイムロス です.
そういうものは事前にコーディングしておいて,コンテスト中はいつでも使える状態にしましょう.
a.go
: コンテスト中に書くコード.UnionFind を使用する.
package main import ( "bufio" "fmt" "os" "a/lib" // 事前に実装してあるデータ構造のライブラリを import ) func main() { r := bufio.NewReader(os.Stdin) w := bufio.NewWriter(os.Stdout) defer w.Flush() var n, m int fmt.Fscan(r, &n, &m) uf := lib.NewUnionFind(n) // import してきたデータ構造「UnionFind」を使う! for i := 0; i < m; i++ { var a, b int fmt.Fscan(r, &a, &b) a-- b-- uf.Union(a, b) } ans := 0 for i := 0; i < n; i++ { if ans < uf.Size(i) { ans = uf.Size(i) } } fmt.Fprintln(w, ans) }
UnionFind
: 事前にコーディングしてある.
package lib type UnionFind struct { par []int } func NewUnionFind(N int) *UnionFind { u := new(UnionFind) u.par = make([]int, N) for i := range u.par { u.par[i] = -1 } return u } func (u UnionFind) Find(x int) int { if u.par[x] < 0 { return x } u.par[x] = u.Find(u.par[x]) return u.par[x] } func (u UnionFind) Union(x, y int) { xr := u.Find(x) yr := u.Find(y) if xr == yr { return } if u.Size(yr) < u.Size(xr) { yr, xr = swap(yr, xr) } u.par[yr] += u.par[xr] u.par[xr] = yr } func (u UnionFind) Same(x, y int) bool { return u.Find(x) == u.Find(y) } func (u UnionFind) Size(x int) int { return -u.par[u.Find(x)] } func swap(a int, b int) (int, int) { return b, a }
gpcg
を使うと,これらのコードを一つにまとめてくれます.
その際,
- パッケージ間で名前が衝突しないように,rename してくれる
- main 関数で使用していない構造体や関数の定義は無視する
などを行ってくれます.
gen.go
:生成されたコード
package main import ( "bufio" "fmt" "os" ) func generated_alib_swap(a int, b int) (int, int) { return b, a } func (u generated_alib_UnionFind) Size(x int) int { return -u.par[u.Find(x)] } func (u generated_alib_UnionFind) Union(x, y int) { xr := u.Find(x) yr := u.Find(y) if xr == yr { return } if u.Size(yr) < u.Size(xr) { yr, xr = generated_alib_swap(yr, xr) } u.par[yr] += u.par[xr] u.par[xr] = yr } func (u generated_alib_UnionFind) Find(x int) int { if u.par[x] < 0 { return x } u.par[x] = u.Find(u.par[x]) return u.par[x] } func generated_alib_NewUnionFind(N int) *generated_alib_UnionFind { u := new(generated_alib_UnionFind) u.par = make([]int, N) for i := range u.par { u.par[i] = -1 } return u } type generated_alib_UnionFind struct{ par []int } func main() { r := bufio.NewReader(os.Stdin) w := bufio.NewWriter(os.Stdout) defer w.Flush() var n, m int fmt.Fscan(r, &n, &m) uf := generated_alib_NewUnionFind(n) for i := 0; i < m; i++ { var a, b int fmt.Fscan(r, &a, &b) a-- b-- uf.Union(a, b) } ans := 0 for i := 0; i < n; i++ { if ans < uf.Size(i) { ans = uf.Size(i) } } fmt.Fprintln(w, ans) } /* this code was generated by the code below package main import ( "bufio" "fmt" "os" alib "a/lib" ) func main() { r := bufio.NewReader(os.Stdin) w := bufio.NewWriter(os.Stdout) defer w.Flush() var n, m int fmt.Fscan(r, &n, &m) uf := alib.NewUnionFind(n) for i := 0; i < m; i++ { var a, b int fmt.Fscan(r, &a, &b) a-- b-- uf.Union(a, b) } ans := 0 for i := 0; i < n; i++ { if ans < uf.Size(i) { ans = uf.Size(i) } } fmt.Fprintln(w, ans) } */
このコードをコピペして提出すると,AC(accepted)を得ることができます
今後の課題
このツールは,実は 未完成 です()
考慮すべきケースを網羅できていなかったり,特定のディレクトリ構造じゃないと panic を起こしたりします.
「お前のツールを使ったから,AtCoder でレートが下がったやんけ」とか言われると怖いです. 普段の精進とかで,遊びで使ってもらえると嬉しいです.
今後は,ツールとして誰かに使ってもらえるようなクオリティーに高めていきます.