勉強し始めて日が浅いので、間違っていることがあれば是非教えて頂きたいです

所感

個人的には競プロ(algo)で言語選択をする場合、以下の点が重要だと考えています

実行速度が早い
- 想定解法を思いついていたのに言語が遅くてTLEしてしまった... は悲しい
  - 高速化してAC出来たとしてもペナルティが痛すぎる
- 想定解法より遅い解法でも実行速度が早い言語なら定数倍高速化により無理矢理AC出来ることもあるので有利
  - 余計なlogをつけても許される確率が高まる
簡潔に書ける
- タイピング量は短い方が実装が早く終わるので有利
- 競プロでは保守性を気にする必要は基本的になく(炎上)、自分が読めたり使えたりしさえすれば良いので、マクロが使えたりコンパイルなども厳しくないほうが良い
標準ライブラリや、ジャッジで使えるライブラリが豊富
- 例えば平衡二分木(set, map)はかなり使う機会がある（これらを使うことが想定解法であることも多い）ので、これらが標準で用意されていないと自分で用意しなければならない
  - しかし平衡二分木は実装がめちゃくちゃ大変なので自分で用意するハードルが高い
他人のライブラリを窃盗出来るか
- 実装が大変なデータ構造やライブラリでも他の人のライブラリをパクってきてACすることはよくあります
  - Luzhild's Library にお世話になっている人は多いのではないでしょうか
  - 人によっては怒られるので注意、ライセンスをよく読むこと
    - 最も競プロにおいては怒られる例をあまり知らないが...

これらの点において golang は

実行速度は？
- 基本的にC++と同等に早く、十分と言える
簡潔に書ける？
- マクロがないので微妙かも？
- AtCoderにおいては2023年のジャッジアップデートで Go 1.20.6 になり generics が使えるようになったためライブラリが作りやすくなった点は良い
ライブラリは豊富？
- AtCoder (Go 1.20.6)
  - 2023年のジャッジアップデートにより結構使えるようになった
    - 特に gostl が追加されたのは大きい
    - これまで golang では gods というデータ構造やアルゴリズムが実装されたライブラリが使えたが、新たに追加された gostl では C++ の STL を意識した実装がされていて、generics を使って実装されているので使いやすいしイテレータもサポートされている
      - 便利な点はあるが不便な点もあり、例えばsetなどはiteratorを指定して要素を削除するメソッドが用意されておらず、multisetを使うときに苦労する可能性が高い
    - golang.org/x/exp/ も追加されていて、slices, constraints とかは便利
    - ACLが使えないのはキツい
- Codeforces (Go 1.19.5)
  - 標準ライブラリ以外何も使えないのでかなり厳しい (詳細)
- yukicoder (Go 1.21.3)
  - Codeforces と同じ？(どこに書いてあるか不明だがオンライン実行で試したところ無さそうだった)
- その他のジャッジ
  - あまり使わないので調べていません
他人のライブラリを窃盗出来るか？
- ACLのgo移植版
  - 全て移植されているわけではない（遅延セグ木とか convolution とか無い）
- Goで競技プログラミングをするときに作っておくと便利な関数 #Go - Qiita
  - 遅延セグ木とか convolution とか dinic などの実装があって参考になるかも
- その他あれば追記するかもしれません

という感じで割と大変だけど無理ではないかなあという感じです詳しい所はちょろっと使ってみただけの私の感想よりGoでAtCoderをやる話 #Go - Qiitaの方が参考になります

後、他人のライブラリを窃盗出来るか？という点について悪いように見えますが、自作を強制されることで理解を深められるという点でメリットであるという見方もできます

ちなみにこんな記事を書いておいて申し訳ないですが golang を普段使いの言語にする予定はないです（でも ISUCON で使うために勉強してみてかなり好きな言語だなと思ったのでたまに気分転換で使うかもしれません）

後、Heuristic については golang で参加したことがないので分かりません

Golang で競プロする時の注意点

先程も紹介させて頂きましたが、Goで競技プログラミングをするときに作っておくと便利な関数 #Go - Qiita ←こちらの記事を参考にしつつ自分で工夫していた点を説明していきます

入出力

入出力はバッファリングしないと遅いのでbufioパッケージを使います。構造体にしておくと便利です。構造体にするついでに、整数列や文字列、グリッドなどの入力やPrintln Printfなどをメソッドとして用意しておくと便利だと思います。

type Io struct {
    In  *bufio.Scanner
    Out *bufio.Writer
}

func NewIo(r io.Reader, w io.Writer) *Io {
    const bufsize = 10000001
    s := bufio.NewScanner(r)
    s.Split(bufio.ScanWords)
    s.Buffer(make([]byte, bufsize), bufsize)
    return &Io{In: s, Out: bufio.NewWriter(w)}
}

func (io *Io) Text() string {
    if !io.In.Scan() {
        panic("failed to Text()")
    }
    return io.In.Text()
}

func (io *Io) NextInt() int {
    x, err := strconv.Atoi(io.Text())
    if err != nil {
        panic("failed to NextInt()")
    }
    return x
}

func (io *Io) NextInt64() int64 {
    x, err := strconv.ParseInt(io.Text(), 10, 64)
    if err != nil {
        panic("failed to NextInt64()")
    }
    return x
}

func (io *Io) NextSliceInt(n int) []int {
    v := make([]int, n)
    for i := 0; i < n; i++ {
        v[i] = io.NextInt()
    }
    return v
}

func (io *Io) NextSliceInt64(n int) []int64 {
    v := make([]int64, n)
    for i := 0; i < n; i++ {
        v[i] = io.NextInt64()
    }
    return v
}

func (io *Io) NextSliceText(n int) []string {
    v := make([]string, n)
    for i := 0; i < n; i++ {
        v[i] = io.Text()
    }
    return v
}

func (io *Io) Println(x ...any) {
    if _, err := fmt.Fprintln(io.Out, x...); err != nil {
        panic("failed to Println()")
    }
}

func (io *Io) Print(x ...any) {
    if _, err := fmt.Fprint(io.Out, x...); err != nil {
        panic("failed to Print()")
    }
}

func (io *Io) Printf(format string, x ...any) {
    if _, err := fmt.Fprintf(io.Out, format, x...); err != nil {
        panic("failed to Printf()")
    }
}

gostl

ドキュメントはこちら↓ pkg.go.dev

GoSTL is a data structure and algorithm library for go, designed to provide functions similar to C++ STL, but more powerful.

として紹介されており、実際実装を読んで見ると本当にそんな感じなので凄いです

ただし全部揃っているわけではないので注意する必要があります

set/multiset

https://pkg.go.dev/github.com/liyue201/gostl@v1.2.0/ds/set

赤黒木で実装されていて、大体 std::set と同じように使えます

ただし注意点としてイテレータを指定して要素を削除するメソッドが用意されていません、なのでmultisetを使う時にとても困ります ~~どうして...~~

一応 issue は立っておりプルリクもあったようなのですがcloseされてしまっていますね

同じ階層に rbtree パッケージがあるので、それを用いて自分で実装して使うのが良さそうですかね？（そもそも set って赤黒木で実装するのが効率良いのかもよく分かってないので、1から自作した方が良い説もあります）

(追記) よく考えたら treemap で代用することも出来ますね

treemap

https://pkg.go.dev/github.com/liyue201/gostl@v1.2.0/ds/map

こちらも赤黒木で実装されており、std::map と同じように使えます

こちらにはイテレータを指定して削除するメソッド（EraseIter）があるので基本的に困らない気がします

実際の使用例：Submission #48893483 - AtCoder Daily Training ALL 2023/10/24 15:30start

priority_queue

https://pkg.go.dev/github.com/liyue201/gostl@v1.2.0/ds/priorityqueue

golang の標準ライブラリにcontainer/heapがあり、これを使うことも出来ますが gostl の方が使いやすいかもしれません

vector

https://pkg.go.dev/github.com/liyue201/gostl@v1.2.0/ds/vector

一応 vector もあるんですけど、C++みたいに演算子オーバーロードがないので...（もちろん普通のプログラミングだと無い方がよいかもしれないのだが、ここは競技プログラミングの世界）

多くの場合 slice で十分な気がします

modint

演算子オーバーロードがある言語じゃないと無理なので諦めるしかなさそうですね...

その他便利関数

generics を使うと良い感じになって嬉しいです

<で比較可能という型制約をどう実装すればいいか分からなかったのでconstraintsパッケージを使っています

func Max[T constraints.Ordered](x, y T) T {
    if x < y {
        return y
    }
    return x
}

func Min[T constraints.Ordered](x, y T) T {
    if x < y {
        return x
    }
    return y
}

func Chmax[T constraints.Ordered](x *T, y T) bool {
    if *x < y {
        *x = y
        return true
    }
    return false
}

func Chmin[T constraints.Ordered](x *T, y T) bool {
    if *x > y {
        *x = y
        return true
    }
    return false
}

func Abs[T constraints.Integer | constraints.Float](x T) T {
    return Max(x, -x)
}

func Reverse[T any](x []T) []T {
    for i, j := 0, len(x)-1; i < j; i, j = i+1, j-1 {
        x[i], x[j] = x[j], x[i]
    }
    return x
}

func Unique[T constraints.Ordered](x []T) []T {
    slices.Sort(x)
    return slices.Clip(slices.Compact(x))
}

感想

Golang は言語仕様がシンプルなので、ライブラリの内部実装を自分でも読むことが出来て楽しい言語だと思っています。

generics に関する仕様を全然理解できてないのでもっと頑張りたいです、これから趣味の範囲で使っていけたらと思います。

memo46

競プロの精進記録その他。

Golang で競プロ

所感