この記事では、AtCoder初心者の方がGoで参加する時に知っておくべき内容を紹介します。
前書き
転職してからここ数ヶ月、会社で開催されている週一のプログラミングコンテスト練習会に参加してきました。
この練習会（プロコン部）ではAtCoderを使用しており、問題を解くための言語を自由に選択できるようになっているため、業務中にメインで使用しているGoを使っています。
これから、GoでAtCoderをやっていきたいプロコン初心者（同志！）のために、問題を解く上で必要になった事を記事としてまとめました。
AtCoderに参加するための準備
- AtCoder にアカウントを作成する
- (出来れば) 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関数
が必要となります。
以下が解答です。
解答
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
入力例
7 3
170
165
150
160
175
180
155
出力例
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を使うのが楽です。- 使いたいsliceの型に
sort.Interfaceを実装してsort.Sortを使っても良いですが、こちらの方が実装がやや面倒になります。
- 使いたいsliceの型に