LoginSignup
5

posted at

updated at

GolangでAtCoder過去問精選10問やってみた。

最近Golangを触り始めました。
基本文法を学んだのでAtCoder過去問精選10問 (AtCoder Beginners Selection)をやってみました。
せっかくなので公開したいと思います。

入門者によるコードのため、Goらしいコードになっているかはわかりませんが、一例となればと思います。
(もっとうまい書き方がありそうな気はしますが・・2重、3重ループしてるとことかとか。)

※問題文についてはリンク先を参照してください。

第0問 WelcometoAtCoder

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)
}
WelcometoAtCoder
$ go run AWelcomeToAtCoder.go
1
2 3
test
6 test

$ go run AWelcomeToAtCoder.go
72
128 256
myonmyon
456 myonmyon

入力を受け取って出力するだけのコードです。
この問題では下部にサンプルがあり、対応している各言語での入力受け取りと出力方法が学べます。
(と言いつつ、以降の問題ではfmt.Scanf以外の入力の受け取り方も使ったりしてます。)

次の問題から実際に解いていく問題になります。

第1問 Product

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")
	}
}
Product
$ go run AProduct.go
3 4
Even

$ go run AProduct.go
1 21
Odd

早速、第0問で使ったfmt.Scanfではなくfmt.Scanを使っています。
フォーマット指定せずに受け取れるのでこれでもいいかなぁと思い、使ってみました。
(ちょっとドキュメントを見るとScanもいろいろ種類があるみたいですね。)

コード自体はよくある条件分岐で判定して出力しているだけです。

第2問 PlacingMarbles

PlacingMarbles
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s string
	fmt.Scanf("%s", &s)
	fmt.Printf("%d\n", strings.Count(s, "1"))
}
PlacingMarbles
$ go run APlacingMarbles.go
101
2

$ go run APlacingMarbles.go
000
0

受け取った文字列に指定の文字がいくつ含まれるかをカウントして出力しています。
Goではstrings.Countで文字列中に含まれる文字をカウントできるので使ってみました。

第3問 Shiftonly

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
}
Shiftonly
$ 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

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)
}
Coins
$ 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

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
}
SomeSums
$ 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

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
}
CardGameforTwo
$ 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

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 {
			// 1つ目は無条件でカウントアップ
			count += 1
		} else if preValue != v {
			// 1つ目以降は前の値と比較し違う場合のみカウントアップ
			count += 1
		}
		preValue = v
	}
	fmt.Println(count)
}
KagamiMochi
$ 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

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
}
Otoshidama
$ 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

白昼夢/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")
	}
}
白昼夢/Daydream
$ 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

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
	}
}
Traveling
$ 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をスタート地点として、各プランへ時間内に移動できるかを確認しながら移動しています。
移動できる条件
tx + 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 - すべての提出

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
5