Goで競技プログラミングをやろう

この記事は Kyash Advent Calendar 2020 7日目の記事です。

最近、競技プログラミング(以下、競プロと略します。)にGo言語で参加していまして、私自身はGoでやる事に特には問題を感じておりませんが、競プロでの経験が少ない方だと言語差など気にする方もいると思いますので、そのへんを説明してみるという記事になります。

結論としては、少なくともAtCoderでGoを使うのはそれほど不利ではないので、Goでやってみたいという方は細かい事を気にせずにチャレンジしてみてください。（どの言語でも良いっていうなら、やはりC++のほうが不便が少ないとは思います。）私は競プロをするようになって、Goに関してはslice周辺への理解が一層深まりました。

競プロの話をする上での前提

まず前提です。ここでいう競プロは特に日本人の参加者も多く、敷居が低いと思われるAtCoderのコンテストを対象としたものになります（他にはCodeforcesや情報オリンピックなど様々なプログラミングコンテストがあります）。また言語差の視点についてですが、こういった競プロではC++が圧倒的に使われていますので、基本的にはC++と比べてどうなのか、という話をします。

競プロを全く知らない、という方はまず試しに例えば以下の問題を解いて、AtCoderのオンラインジャッジシステムに触れてみると良いでしょう。ユーザ登録してページ末尾のフォームからソースコードをSubmitすることで回答することができます。（ちなみにこの問題は最も簡単な部類であり、問題文が理解できれば題意を率直に実装するだけで良いので、競プロ的な難しさや楽しさなどは全くありません。あくまでオンラインジャッジシステムを知るための例としてとらえてください。） atcoder.jp

Goは遅くて不利？

まず不安視される点として、Goは遅くて不利なんじゃないか、というような点があるかと思います。しかし、競技プログラミングで不利になるような遅さではありません。遅さのせいでC++より解き辛くなるような問題を見つけるのは困難でしょう。

Goには、ランタイムやGCなどのオーバーヘッドがあり、オーバーヘッドを除いた実行速度でもC++の倍ぐらい遅いこともあるかもしれません。しかし、仮に数倍程度遅かったとしても競プロにおいてはほとんど問題ありません。

このあたりをある程度納得するには計算量についての理解が必要となってきます。また、AtCoderでは1秒あたり $10^{8}$ 回くらいのステップを実行でき、問題の入力で与えられるデータ数は多くておおよそ $10^{5}$ 個、実行時間制限は例えば2秒以内となっています。このデータ数を $n$ としたとき、仮に時間計算量が $O(n^{2})$ になるような実装をしてしまうと制限時間には絶対に間に合いません。 $n^{2}$ が最大で [tex: 10¹⁰] なので、100秒かかってしまうと見積もれるからですね。計算量を改善しない限り、いくらその他の細かな最適化を行っても到底そこから100倍速とはならず、間に合いません*1。よってより効率的な解法を考え、例えば $O(n)$ や $O(n \log^{2} n)$ などの計算量になる実装をしなくてはいけません。これはどのプログラミング言語を使ってもほぼ同様です。なぜなら言語間の差はオーダー記法でいうと定数倍の差しか作らないからです*2。

例えば以下の問題は、そういった計算量の知識なしに解いてしまうと、なぜ時間制限をオーバーしてしまうのかわからなくなってしまうと思います。なお、この問題に関しては入力のバッファリングも必要になります。バッファリングについては本記事内でやり方を説明します。

atcoder.jp

以下のようなループをするコードを書いてしまうと、[tex: 10¹⁰]ステップを軽く超え、やはり制限時間には到底間に合いません。

var n, w int
fmt.Scan(&n, &w)
for i := 0; i < n; i++ {
    var s, t, p int
    fmt.Scan(&s, &t, &p)
    for ; s < t; s++ {
        // ここがトータルで 10^10 回以上実行されることになる。
    }
}

以上のように、制限時間に間に合うような解法を「考察」して見つける、というのが競プロでいつもやらなければいけない事でして、簡単すぎる問題でなければ、競技中はここに最も時間を割きます。この「考察」においては言語間の差は著しく低いでしょう。

C++は標準ライブラリが便利そうだが、Goの標準ライブラリは不利？

ライブラリについては、C++のほうがわずかに有利といえるでしょう。

標準ライブラリの差という点でGoで最も不利を感じるのは、Ordered Mapの欠如でしょう。例えばC++であれば std::map::lower_bound を使って、 std::map 内の特定のキーから近い別のキーを取得することができますが、Goの map は順序付けされていないのでそういったことができません。しかし AtCoder の実行環境においては、 https://github.com/emirpasic/gods という外部ライブラリを使うことができます*3 ので、そのRedBlackTreeを利用すれば、C++のstd::mapと同様の操作が可能です。(とはいえ、やはり組み込みで用意されている slice や map などの使い心地には及びません。)

また、 AtCoderが最近公開したAtCoder LibraryというC++のアルゴリズムライブラリがありますが、もちろんC++以外では利用できません*4。ただ、このようなアルゴリズムライブラリはそもそも学習しながら自分で準備しておくべきもの、といえると思いますし、もっと様々なコードをスニペットとして準備しておけばいざというときに有利になります。

Goの良いところはある？

些細な事ではありますが、しばしばGoでよかったと思える部分を挙げておきます。

AtCoderのジャッジシステムは64bit環境でありint型が64bitサイズになっているため、int64型をわざわざ使い分けなくて良いのは楽です。
sliceの先頭と末尾からであれば要素を $O(1)$ で削除できます*5。C++では std::vector で先頭削除をやろうとすると遅いので、代わりに std::listやstd::deque を使ったり、先頭を指すインデックスを用意しておいてそれをずらすことで表現するでしょう。
関数が多値を返すことができます。C++でも std::tuple を使えば同様のことができますが、Goのように言語組み込みの機能であれば、より使いやすいです。
Golandからであれば、テストを生成し、デバッガを使ったデバッグがやりやすいです。

Goで挑戦するなら、まずは入出力をバッファリングするやり方を覚えよう

先ほど、入力が多い場合は $10^{5}$ 個になる、ということを書きましたが、こういった大量の入出力をするためにはバッファリングをしないと実行時間制限に間に合わなくなります。なおバッファリングをしないと間に合わない、というのはGoに限ったことではなく他の言語でも同じ事です。

Goでバッファリングをするには基本的には bufio.NewReader と bufio.NewWriter を使えばよいでしょう。これを使って例えば先程の atcoder.jp を解くと以下のようになります。

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush() // バッファリングしているので、最後に確実に Flush して出力させます。

    var n, w int
    fmt.Fscan(in, &n, &w) // 入力

    sum := make([]int, 2*1e5+2)
    for i := 0; i < n; i++ {
        var s, t, p int
        fmt.Fscan(in, &s, &t, &p) // 入力
        sum[s] += p
        sum[t] -= p
    }
    for i := 0; i < 2*1e5+1; i++ {
        sum[i+1] += sum[i]
    }
    for i := 0; i < 2*1e5+2; i++ {
        if sum[i] > w {
            fmt.Fprintln(out, "No") // 出力
            return
        }
    }
    fmt.Fprintln(out, "Yes") // 出力
}

バッファサイズをもっとチューニングしたり、 bufio.Scanner を使ったりなどすれば、さらに高速化することはできますが、そこまでせずとも bufio.NewReader と bufio.NewWriter で速度的には十分です。

よく使うGoの標準ライブラリ

参考までに、私が特に競プロで使う標準ライブラリを挙げておきます。

sort パッケージ
- sort.Ints
- sort.Float64s
- sort.Strings
- sort.Sort
- sort.Slice
- sort.Search
- sort.SearchInts
container/heap パッケージ
- 優先度付きキューの実装に使います。
container/list パッケージ
- デック(Deque)の実装に使います。
math パッケージ
- math.Hypot
math/bits パッケージ
- bits.OnesCount

AtCoder 以外のコンテストはどうなのか？

ICPC、情報オリンピック、TopCoder においてはGoは使えません。
CodeForces、Google Code Jam、Facebook Hacker Cup、CodeChef、Aizu Online Judge、LeetCode、YukiCoder では使うことができます。ただしGoのバージョンが古かったりはしますし、https://github.com/emirpasic/godsを利用することもできません。AtCoderでGoを使うのとは勝手が違ってきますのであらかじめご確認ください。

*1:例えば、ありがちな些細な最適化としては、関数をインライン化する、変数を減らす、のようなやつでしょう。

*2:一部のスクリプト言語などかなり遅い処理系の場合は、この定数倍が大きすぎて問題になることもあるかもしれません。

*3:詳しくは、Language Test 202001 - AtCoderにある表のうちGoの項目を参照してください。他にはhttps://github.com/gonum/gonumを利用できます。

*4:有志の方で移植されている https://github.com/monkukui/ac-library-go はありますが、まだ不足しているといえます。発展させたいですね。

*5:sliceはいろんな操作ができます。参考: https://github.com/golang/go/wiki/SliceTricks

Evolutionary Architectures

takezawa's blog