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

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

## 前書き

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

## AtCoderに参加するための準備

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

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

## 基本編

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

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

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

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

### 例題

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

#### 入力

```
N
```

#### 出力

```
Child or Adult
```

#### 入力例

```
15
```

#### 出力例

```
Child
```

### やる事

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

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

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

* main packageの宣言
* main関数

が必要となります。

以下が解答です。

### 解答

```go
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` を入力する、と指定されたら、

```go
var x, n int
fmt.Scan(&x, &n)
```
とするだけでOKです。

#### stringを入力する場合

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

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

### 入力がN回行われる場合

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

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

#### 入力

```
N X
T1
...
Tn
```

#### 出力

```
Tmin1
...
Tminx
```

#### 入力例

```
7 3 
170
165
150
160
175
180
155
```

#### 出力例

```
150
155
160
```

### やる事

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

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

```go
// 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`](https://golang.org/pkg/sort/#Ints)を使えばOKです。

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

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

### 解答

```go
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](https://practice.contest.atcoder.jp/)
  - B問題のInteractiveは滅多に出ないので、A問題だけでOKです
* [AtCoder Beginner Selection](https://abs.contest.atcoder.jp/)


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