Goで始めるAtCoderのススメ（初心者向け） #Go

この記事では、AtCoder初心者の方がGoで参加する時に知っておくべき内容を紹介します。

前書き

転職してからここ数ヶ月、会社で開催されている週一のプログラミングコンテスト練習会に参加してきました。
この練習会（プロコン部）ではAtCoderを使用しており、問題を解くための言語を自由に選択できるようになっているため、業務中にメインで使用しているGoを使っています。
これから、GoでAtCoderをやっていきたいプロコン初心者（同志！）のために、問題を解く上で必要になった事を記事としてまとめました。

AtCoderに参加するための準備

AtCoder にアカウントを作成する
(出来れば) Go 1.6 (2018年現在) の環境を用意する
- AtCoderのオンラインジャッジ環境が Go 1.6 のため… 😢

AtCoderアカウントは、実はこの記事の内容を実行するだけなら不要ですが、ぜひ初めに登録しておきましょう！

基本編

AtCoderを始めとする、オンラインジャッジ形式のプログラミングコンテストのサイトでは、

ある値を標準入力から受け取る
受け取った値を使用して、標準出力に回答を出力する

のが基本的な操作となります。

次のような例題を解くことを考えてみましょう。

例題

年齢 N が20より小さければ Child, 20以上であれば Adult と表示しなさい。

入力

出力

Child or Adult

入力例

出力例

Child

やる事

N を int として受け取り、20 と比較出来ればOKです。

標準入力から fmt.Scan で受け取る
標準出力に fmt.Println で書き出す
- 末尾に改行が必要なので、fmt.Printlnを使います

また、解答は、完全に動作するコードである必要があるので、

main packageの宣言
main関数

が必要となります。

以下が解答です。

解答

package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)

    if n < 20 {
        fmt.Println("Child")
        return
    }

    fmt.Println("Adult")
}

複数の入力がある場合

fmt.Scan() は、複数の変数を受け取れるので、
X, N を入力する、と指定されたら、

var x, n int
fmt.Scan(&x, &n)

とするだけでOKです。

stringを入力する場合

変数の宣言を string にするだけでOKです。

var (
    n int
    s string
)
fmt.Scan(&n, &s)

入力がN回行われる場合

次のような問題があったとします。

Qiita高校には、 N 人の生徒がいます。
Qiita高校の生徒の身長はそれぞれ Ti です。
生徒を身長の低い順に並べた時、初めの X 人の身長を低い順で一行ずつ表示しなさい。

入力

N X
T1
...
Tn

出力

Tmin1
...
Tminx

入力例

出力例

150
155
160

やる事

素直に slice を用意して、for文を使って値を保存していく
sort packageを使って、sliceをソートする

sliceにはいくつか使い方がありますが、サイズを指定せずappendしていくやり方だと、capacity増加時のコストが予測出来ないため、初めからサイズを指定しておいた方が良いです。

// Not good
var t []int
for i := 0; i < n; i++ {
    var tmp int
    fmt.Scan(&tmp)
    t = append(t, tmp)
}

// Good
t := make([]int, n)
for i := 0; i < n; i++ {
    fmt.Scan(&t[i])
}

sort package には、sliceのソートを行うための関数がいくつか用意されています。
今回は、入力が int のsliceなので、sort.Intsを使えばOKです。

t := make([]int, n)
for i := 0; i < n; i++ {
...
}
sort.Ints(t)

sort.Ints は int を昇順に並び替えてくれます。
sort.Ints は十分に速いので (計算量 O(n*log(n)) )、int の並び替えであれば基本的にこれを使えば良いです。

解答

package main

import (
    "fmt"
    "sort"
)

func main() {
    var n, x int
    fmt.Scan(&n, &x)

    t := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&t[i])
    }
    sort.Ints(t)

    for i := 0; i < x; i++ {
        fmt.Println(t[i])
    }
}

今回は、ソートを行う必要があったのでsliceに値を保存しましたが、
単純な問題では、全ての値を保持しておく必要が無いケースも多いので、時と場合に応じて使うようにしてください。

`fmt.Scan` を使う上での注意

fmt.Scan は内部的に reflect packageを使用しており、実行コストが高いため、
入力する変数が非常に多い場合、制限時間内に入力が間に合わない場合があります。
入力数が 10^9 程度であれば十分に実行可能ですが、それを超える場合は bufio.Scanner を使った入力の実装を検討してください。

最後に

ここまでの内容がわかれば、A問題は確実に解けるはずです！
AtCoder Beginner Contestには、D問題まであり、難易度に応じて点数が上がっていきます。
初めはBまでを目標にして練習して、C, D問題を解けるようになっていきましょう！
（自分もD問題を安定して解けるようになりたい！）

手始めに、下記の2つをやってみることをオススメします！
Practice Contestは、ほぼ提出の練習しか無いので、10分くらいあれば十分です。

AtCoder Practice Contest
- B問題のInteractiveは滅多に出ないので、A問題だけでOKです
AtCoder Beginner Selection

sort packageに関する補足

sort.Ints は内部的に sort.Sort を呼び出しており、これがQuick Sortを使用しているため上記の計算量となります。 (正確には、sliceの長さに応じて別のソート方法も使用しています: 実装)
sort.Sort は安定ソートでは無いので、安定ソートを使いたければ sort.Stable を使うと良いです。
sort packageに初めから関数として用意されているのは、sort.Ints, sort.Float64s, sort.Strings のみなので、それ以外の型を扱う場合は ~~sort.Slice を使うのが楽です。~~ (← go 1.6にはありませんでした…)
- 使いたいsliceの型に sort.Interface を実装して sort.Sort を使っても良いですが、こちらの方が実装がやや面倒になります。

Goで始めるAtCoderのススメ（初心者向け）

前書き