最近Golangを触り始めました。
基本文法を学んだのでAtCoder過去問精選10問 (AtCoder Beginners Selection)をやってみました。
せっかくなので公開したいと思います。
入門者によるコードのため、Goらしいコードになっているかはわかりませんが、一例となればと思います。
(もっとうまい書き方がありそうな気はしますが・・2重、3重ループしてるとことかとか。)
※問題文についてはリンク先を参照してください。
第0問 WelcometoAtCoder
package main
import (
"fmt"
)
func main() {
var a, b, c int
var s string
fmt.Scanf("%d", &a)
fmt.Scanf("%d %d", &b, &c)
fmt.Scanf("%s", &s)
fmt.Printf("%d %s\n", a+b+c, s)
}
$ go run AWelcomeToAtCoder.go
1
2 3
test
6 test
$ go run AWelcomeToAtCoder.go
72
128 256
myonmyon
456 myonmyon
入力を受け取って出力するだけのコードです。
この問題では下部にサンプルがあり、対応している各言語での入力受け取りと出力方法が学べます。
(と言いつつ、以降の問題ではfmt.Scanf以外の入力の受け取り方も使ったりしてます。)
次の問題から実際に解いていく問題になります。
第1問 Product
package main
import (
"fmt"
)
func main() {
var a, b int
fmt.Scan(&a, &b)
product := a * b
if product%2 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}
}
$ go run AProduct.go
3 4
Even
$ go run AProduct.go
1 21
Odd
早速、第0問で使ったfmt.Scanfではなくfmt.Scanを使っています。
フォーマット指定せずに受け取れるのでこれでもいいかなぁと思い、使ってみました。
(ちょっとドキュメントを見るとScanもいろいろ種類があるみたいですね。)
コード自体はよくある条件分岐で判定して出力しているだけです。
第2問 PlacingMarbles
package main
import (
"fmt"
"strings"
)
func main() {
var s string
fmt.Scanf("%s", &s)
fmt.Printf("%d\n", strings.Count(s, "1"))
}
$ go run APlacingMarbles.go
101
2
$ go run APlacingMarbles.go
000
0
受け取った文字列に指定の文字がいくつ含まれるかをカウントして出力しています。
Goではstrings.Countで文字列中に含まれる文字をカウントできるので使ってみました。
第3問 Shiftonly
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
var n int
fmt.Scanf("%d", &n)
stdin := bufio.NewScanner(os.Stdin)
stdin.Scan()
s := stdin.Text()
split := strings.Split(s, " ")
list := convStringListToIntList(split)
count := 0
for {
if !isEvenNumberList(list) {
break
}
list = divideByTwo(list)
count += 1
}
fmt.Println(count)
}
func convStringListToIntList(list []string) []int {
newList := make([]int, len(list))
for i, v := range list {
a, _ := strconv.Atoi(v)
newList[i] = a
}
return newList
}
func divideByTwo(list []int) []int {
newList := make([]int, len(list))
for i, v := range list {
newList[i] = v / 2
}
return newList
}
func isEvenNumberList(list []int) bool {
result := true
for _, v := range list {
if v%2 != 0 {
result = false
break
}
}
return result
}
$ go run BShiftOnly.go
3
8 12 40
2
$ go run BShiftOnly.go
4
5 6 8 10
0
$ go run BShiftOnly.go
6
382253568 723152896 37802240 379425024 404894720 471526144
8
fmt.Scanfで入力1行目のNを読み込んでいますが、コードでは使用しません。
bufio.NewScannerからの3行のコードで入力2行目を丸々取得しています。
strings.Split(s, " ")でスペース区切りで分割したリストとして取得しています。
文字として取得しているのでstrconv.Atoiを使って数値に変換しています。
その後は、偶数チェックし偶数の場合、2で割ったものに置き換える処理をしつつカウントして、
条件に合わなくなった段階でループを抜けてカウント結果を出力しています。
※ごり押しで解いてしまいましたが、本来はビット演算を使用するのがセオリーのようです。
第4問 Coins
package main
import (
"fmt"
)
func main() {
var a, b, c, x int
fmt.Scanf("%d", &a)
fmt.Scanf("%d", &b)
fmt.Scanf("%d", &c)
fmt.Scanf("%d", &x)
count := 0
for va := 0; va <= a; va++ {
for vb := 0; vb <= b; vb++ {
for vc := 0; vc <= c; vc++ {
sum := va*500 + vb*100 + vc*50
if sum == x {
count += 1
}
}
}
}
fmt.Println(count)
}
$ go run BCoins.go
2
2
2
100
2
$ go run BCoins.go
5
1
0
150
0
$ go run BCoins.go
30
40
50
6000
213
愚直に全通り計算しています。
条件に合う場合にカウントして、最後に結果を出力しています。
3重ループになってしまっている。
第5問 SomeSums
package main
import (
"fmt"
"strconv"
"strings"
)
func main() {
var n int
var a int
var b int
fmt.Scanf("%d %d %d", &n, &a, &b)
var count int
for i := 1; i <= n; i++ {
x := sumNumber(strconv.Itoa(i))
if aOrMoreAndBOrLess(a, b, x) {
count += i
}
}
fmt.Println(count)
}
func sumNumber(s string) int {
numbers := strings.Split(s, "")
var sum int
for _, sv := range numbers {
iv, _ := strconv.Atoi(sv)
sum += iv
}
return sum
}
func aOrMoreAndBOrLess(a, b, x int) bool {
result := false
if a <= x && x <= b {
result = true
}
return result
}
$ go run BSomeSums.go
20 2 5
84
$ go run BSomeSums.go
10 1 2
13
$ go run BSomeSums.go
100 4 16
4554
こちらもごり押しで、1からNの整数を順にチェックしています。
strconv.Itoaで数値を文字列にしてstrings.Split(s, "")で桁ごとに分けて合計しています。
合計するときはstrconv.Atoiで数値に戻して加算しています。
A以上かつB以下である場合カウントして、最後は出力して終わりです。
第6問 CardGameforTwo
package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
"strings"
)
func main() {
var n int
fmt.Scan(&n)
stdin := bufio.NewScanner(os.Stdin)
stdin.Scan()
s := stdin.Text()
split := strings.Split(s, " ")
intList := convStringListToIntList(split)
sort.Sort(sort.Reverse(sort.IntSlice(intList)))
alice, bob := assignToAliceAndBob(intList)
aliceSum := sum(alice)
bobSum := sum(bob)
fmt.Println(aliceSum - bobSum)
}
func convStringListToIntList(stringList []string) []int {
intList := make([]int, len(stringList))
for i, v := range stringList {
iv, _ := strconv.Atoi(string(v))
intList[i] = iv
}
return intList
}
func assignToAliceAndBob(list []int) ([]int, []int) {
aliceList := make([]int, len(list))
bobList := make([]int, len(list))
c := 0
for i, v := range list {
if i%2 == 0 {
aliceList[c] = v
} else {
bobList[c] = v
}
c += 1
}
return aliceList, bobList
}
func sum(list []int) int {
var result int
for _, v := range list {
result += v
}
return result
}
$ go run BCardGameForTwo.go
2
3 1
2
$ go run BCardGameForTwo.go
3
2 7 4
5
$ go run BCardGameForTwo.go
4
20 18 2 18
18
第3問と同じ方法で入力を取得しています。
「得点を最大化するように最適な戦略を取れるカードの中から最大のものを取る。」と仮定して解きました。
sort.Sort(sort.Reverse(sort.IntSlice(intList)))を使用して降順に並べ替えています。
ソートしたカード一覧をAliceとBobに分けて、合計結果から差分を求め出力しています。
第7問 KagamiMochi
package main
import (
"fmt"
"sort"
)
func main() {
var n int
fmt.Scanf("%d", &n)
mochiList := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scanf("%d", &mochiList[i])
}
sort.Sort(sort.IntSlice(mochiList))
var count int
preValue := 0
for _, v := range mochiList {
if preValue == 0 {
// １つ目は無条件でカウントアップ
count += 1
} else if preValue != v {
// 1つ目以降は前の値と比較し違う場合のみカウントアップ
count += 1
}
preValue = v
}
fmt.Println(count)
}
$ go run BKagamiMochi.go
4
10
8
8
6
3
$ go run BKagamiMochi.go
3
15
15
15
1
$ go run BKagamiMochi.go
7
50
30
50
100
50
80
30
4
入力1行目の数だけループして入力を取得しています。
餅の一覧をソートして、順に前の餅のサイズと比較し重ねられるかを判断してカウントしています。
1つ目の餅は前の餅がないので無条件でカウントしています。
第8問 Otoshidama
package main
import (
"fmt"
// "time"
)
func main() {
var n, y int
fmt.Scanf("%d %d", &n, &y)
// at := time.Now()
fmt.Println(checkNumbers(n, y))
// fmt.Println(time.Since(at))
}
func checkNumbers(n, y int) (int, int, int) {
for a := 0; a <= n; a++ {
for b := 0; b <= n; b++ {
sum := 10000*a + 5000*b + 1000*(n-a-b)
if (n - a - b) >= 0 {
if sum == y {
return a, b, (n - a - b)
}
}
}
}
// 全件チェックして見つからなかった場合は固定値返却
return -1, -1, -1
}
$ go run COtoshidama.go
9 45000
0 9 0
$ go run COtoshidama.go
20 196000
-1 -1 -1
$ go run COtoshidama.go
1000 1234000
2 54 944
$ go run COtoshidama.go
2000 20000000
2000 0 0
この問題もごり押し気味にチェックしています。
ただし、3重ループにするとタイムアウトしてしまうので、
合計枚数と10000円札の枚数、5000円札の枚数から1000円札の枚数を求めるようにして計算量を減らしています。
第9問 白昼夢/Daydream
package main
import (
"fmt"
"strings"
)
func main() {
var s string
fmt.Scan(&s)
s = strings.Replace(s, "dream", "D", -1)
s = strings.Replace(s, "erase", "E", -1)
s = strings.Replace(s, "Der", "", -1)
s = strings.Replace(s, "Er", "", -1)
s = strings.Replace(s, "D", "", -1)
s = strings.Replace(s, "E", "", -1)
s = strings.TrimSpace(s)
if s == "" {
fmt.Println("YES")
} else {
fmt.Println("NO")
}
}
$ go run CDayDream.go
erasedream
YES
$ go run CDayDream.go
dreameraser
YES
$ go run CDayDream.go
dreamerer
NO
文字列Tがdream, dreamer, erase, eraserから構成されていること、
「dreamer = dream + er」、「eraser = erase + r」であることを利用しています。
文字列SをTの構成要素のみかをチェックするために、strings.Replaceを使って順に空文字に変換しています。
空文字になった場合はYES。文字が残った場合はNoとして出力しています。
第10問 Traveling
package main
import (
"fmt"
"math"
)
func main() {
var n int
fmt.Scanf("%d", &n)
plans := make([][]float64, n+1)
// 旅行プランの始点を追加
plans[0] = []float64{0, 0, 0}
var t, x, y float64
for i := 1; i < n+1; i++ {
fmt.Scanf("%f %f %f", &t, &x, &y)
plans[i] = []float64{t, x, y}
}
canBeMove := true
var tt, xx, yy float64
for i := 1; i < n+1; i++ {
tt = math.Abs(float64(plans[i][0] - plans[i-1][0]))
xx = math.Abs(float64(plans[i][1] - plans[i-1][1]))
yy = math.Abs(float64(plans[i][2] - plans[i-1][2]))
movingDistance := xx + yy
if isEvenNumber(movingDistance) {
// x+y(移動距離)が偶数の場合、tが偶数かつx+y以上であれば可能
// (tが奇数またはx+y以下の場合は不可)
if !isEvenNumber(tt) || tt < movingDistance {
canBeMove = false
break
}
} else {
// x+y(移動距離)が奇数の場合、tが奇数かつx+y以上であれば可能
// (tが偶数またはx+y以下の場合は不可)
if isEvenNumber(tt) || tt < movingDistance {
canBeMove = false
break
}
}
}
if canBeMove == true {
fmt.Println("Yes")
} else {
fmt.Println("No")
}
}
func isEvenNumber(number float64) bool {
if int(number)%2 != 0 {
return false
} else {
return true
}
}
$ go run CTraveling.go
2
3 1 2
6 1 1
Yes
$ go run CTraveling.go
1
2 100 100
No
$ go run CTraveling.go
2
5 1 1
100 1 1
No
こちらもややごり押し？しています。
0，0をスタート地点として、各プランへ時間内に移動できるかを確認しながら移動しています。
移動できる条件
・tはx + y(移動距離)以上
・x + y(移動距離)が偶数の場合はtも偶数
・x + y(移動距離)が奇数の場合はtも奇数
移動できない場合は確認を終了しています。
この解法で合っているかちょっと自信ありませんでしたが、ACになりました。。
やってみた感想。
なかなか解法が思いつかない問題もあって苦戦しましたが、
他者のコードを参考にしつつ、何とか全問AC取ることができたので良かったです。
もう少し他の問題で練習したら、コンテストにも参加してみようかと思います。
(AtCoder Problems、まずはA,Bをさくさく解けるようにしたい。。)
競技プログラミングは言語を入門する際にも、とてもいい教材ですね。
ガシガシ解いてコーディング力を上げて行きたいです。
※ところで、変数名にlistを使っていますが、正確にはsliceなのでダメな変数名かもですね。。
今回は以上です。
参考
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
golang.org - Packages
golang.jp - パッケージドキュメント ※古めです。英語ドキュメント理解の補助に。
AtCoder Beginners Selection - すべての提出