Go言語でAtCoderに参加する場合の注意点|テンプレートも公開
はじめに
Go言語でAtCoderをやっている人なんてあまりいないので需要がないとは思うけど、Go言語で参加する場合はいくつか注意点があります。これから、Go言語で挑戦しようとしている方は参考にしてください。
私が使っているテンプレート貼っておきますので、よろしければ使ってください。これをベースに自分っぽくカスタムするのも良いかと思います。
その他のAtCoderに役立つ記事の一覧は以下にあります。
入出力に関して
標準関数が遅い
Go言語の標準のfmt.Scan()
、fmt.Println()
などの関数は、結構遅いです。入力が少ない場合は、いいのですが、入力が多くなると、読み込みだけで相当な時間がかかってしまいます。
実際、AtCoderの問題を解き始めた頃、入力が遅いせいでTLEになったということがありました。原因が全然わからないので悩みました。
アルゴリズム上の実装ミスを疑って、まさか標準入力が遅いとか思わないですから・・・
ちなみに、Printlnが遅いのは、毎回入力をflushしているからです。出力毎にバッファクリアされるのでかなり遅い・・・。これを解消するには、fmt.Fprintln
などのファイルへの書き出し関数を使います。こちらを使うと、バッファリングされて一気に書き出されるようになり、見違えるほど速くなります。
インタラクティブ問題では、バッファリングされてしまうので、fmt.Fprintlnを使う場合は、明示的にflushする方が良いです。
fmt.Scan
は、bufioという標準のライブラリを使って読み込む方法が良いかと思います。ただ、こちらもデフォルトで使うとトラブります。
bufioには、一度に読み込める文字数に制限がある
読み込み速度を高速化するために、bufioというライブラリを利用できるのですが、デフォルトではバッファサイズが小さくて、一度に読み込める文字数に制限があるという罠があります。
このため、出題によっては、1行が読み込めずに途中で切れてしまいます。
これについては、バッファサイズを変更することで対応できますが、知らないとハマります。
標準入出力でハマるというのは結構罠です。最初悩みました。
標準で用意されている関数について
min, maxさえ無い
他の言語では普通に使える関数が結構存在していません。例えば、min, maxでさえ用意されていません。このあたり、毎回作っていると手間です。
テンプレートを作っておくことをおすすめ
テンプレート例
Go言語でAtCoderに参加している人をみると、結構な確率でテンプレートを使われています。
ということで、自分が使っているテンプレートをここに貼っておきます。
テンプレートを使うと、入力や出力関連を気にしなくてよいので楽です。
整数、浮動小数、文字列の入力関数としてgetI(), getF(), getS()
、連続した整数の読み込み用のgetInts()
、Printlnの代わりのout()
、補助関数として、min, max, nmin, nmax, chmin, chmax, asub, abs
、C++っぽいlowerBound, upperBound
を用意しています。
また、main関数の先頭でバッファの設定をしています。
2年ほどこのテンプレートを使ってやっていますが、とりあえず問題なく解答できていますのでおそらく使って大きなトラブルはないと思います。
これを自分用にカスタムするのも良いかと思います。
package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
"strconv"
)
var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)
func out(x ...interface{}) {
fmt.Fprintln(wr, x...)
}
func getI() int {
sc.Scan()
i, e := strconv.Atoi(sc.Text())
if e != nil {
panic(e)
}
return i
}
func getF() float64 {
sc.Scan()
i, e := strconv.ParseFloat(sc.Text(), 64)
if e != nil {
panic(e)
}
return i
}
func getInts(N int) []int {
ret := make([]int, N)
for i := 0; i < N; i++ {
ret[i] = getI()
}
return ret
}
func getS() string {
sc.Scan()
return sc.Text()
}
// min, max, asub, absなど基本関数
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
// min for n entry
func nmin(a ...int) int {
ret := a[0]
for _, e := range a {
ret = min(ret, e)
}
return ret
}
// max for n entry
func nmax(a ...int) int {
ret := a[0]
for _, e := range a {
ret = max(ret, e)
}
return ret
}
func chmin(a *int, b int) bool {
if *a < b {
return false
}
*a = b
return true
}
func chmax(a *int, b int) bool {
if *a > b {
return false
}
*a = b
return true
}
func asub(a, b int) int {
if a > b {
return a - b
}
return b - a
}
func abs(a int) int {
if a >= 0 {
return a
}
return -a
}
func lowerBound(a []int, x int) int {
idx := sort.Search(len(a), func(i int) bool {
return a[i] >= x
})
return idx
}
func upperBound(a []int, x int) int {
idx := sort.Search(len(a), func(i int) bool {
return a[i] > x
})
return idx
}
func main() {
defer wr.Flush()
sc.Split(bufio.ScanWords)
sc.Buffer([]byte{}, math.MaxInt32)
// this template is new version.
// use getI(), getS(), getInts(), getF()
}
追加(2024/03/10)
N個が指定されていない場合
AtCoder Beginner Contest 344 B問題に、入力数Nが指定されていないパターンが出題されました。最後が0で終わるパターンだったので0かどうか判定すればよかったですが、入力数が指定されていない場合は、以下のような関数で最後の入力かどうかを判断できます。
下記コードは整数を読み込みますが、2つ目の引数が読み込んだかどうかのフラグになっています(falseの場合は、終了)。
sc.Scan()
の戻り値を利用しています
func getIf() (int, bool) {
ret := sc.Scan()
if ret == false {
return -1, false
}
i, e := strconv.Atoi(sc.Text())
if e != nil {
panic(e)
}
return i, true
}
参考にした記事とか
競プロを始めた時、なぜ正解できないのか悩みました。色々記事を探したと思いますが、当時見た記憶があるリンクを貼っておきます。他にも、いくつか見た記憶はあるのですが、探しても見つからなかったので1つだけ貼っておきます。
情報がなければきっとハマりまくってたと思います。非常に助かった記憶があります。
【Golang】fmt.Scanとbufio.Scannerの速度比較
AtCoder参加に役立つライブラリなど
頻繁に使うデータ構造のスタック・キュー、優先キューや、NextPermutation, UnionFindなど、いくつかのデータ構造・アルゴリズムについて記事にしています。そちらの記事も読んでみてください。
まとめ
Go言語を使っている人が少ないので、情報も少ないです。また、ライブラリもあまり完備されていないので自作する必要もあります。
Go言語を競プロで使う人が増えたら良いなと思っているので、自分が使っているコードなどを時々紹介していきたいと思います。