post Image
Goで始めるAtCoderのススメ(初心者向け)

この記事では、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.Intsint を昇順に並び替えてくれます。
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分くらいあれば十分です。

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 を使っても良いですが、こちらの方が実装がやや面倒になります。

『 Go 』Article List
Category List

Eye Catch Image
Read More

Androidに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

AWSに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Bitcoinに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

CentOSに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

dockerに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

GitHubに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Goに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Javaに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

JavaScriptに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Laravelに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Pythonに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Rubyに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Scalaに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Swiftに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Unityに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Vue.jsに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Wordpressに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

機械学習に関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。