A Tour of GoでGoを勉強して、ちょっと手を動かすかと思ったら、有志の方の素晴らしい教材があったので、やってみることに。
問題の詳しい解説は元のエントリが詳しいので是非見てみてください！
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita
※後でよく考えたら二番煎じかと思って調べてみたら、すでに素敵なエントリがありました笑
AtCoder に登録したら解くべき精選過去問 10 問を Go で解いてみた - Qiita
とはいえ解き方が違う問題もあるので、置いておきますね
第 1 問: ABC 086 A - Product (100 点)
最近PHPとかRuby書いてたので、それに比べるとgoの標準入出力難しいｗ
※fmt.Scanは改行だけでなく空白も区切るので注意
ちなみにGoの標準入力は以下が最高に詳しいです！
package main
import (
"fmt"
)
func main() {
var a, b int
fmt.Scan(&a, &b)
if product := a * b; product%2 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}
}
第 2 問: ABC 081 A - Placing Marbles (100 点)
for使わなくても解けるのですが、普通にfor使いましたｗ
package main
import (
"fmt"
)
func main() {
var (
a string
count = 0
)
fmt.Scan(&a)
for i := 0; i < len(a); i++ {
if a[i] == '1' {
count++
}
}
fmt.Println(count)
}
第 3 問: ABC 081 B - Shift Only (200 点)
素直に解くとこんな感じ？
package main
import (
"fmt"
)
func main() {
var (
n int
count int
)
fmt.Scan(&n)
nums := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&nums[i])
}
flag := true
for flag {
for i := 0; i < n; i++ {
if nums[i]%2 == 0 {
nums[i] /= 2
} else {
flag = false
}
}
if flag {
count++
}
}
fmt.Println(count)
}
関数分けたり、標準入力にbufio使うver
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func checkEven(a []int) bool {
for i := 0; i < len(a); i++ {
if a[i]%2 != 0 {
return false
}
}
return true
}
var sc = bufio.NewScanner(os.Stdin)
func nextLine() string {
sc.Scan()
return sc.Text()
}
func main() {
nextLine()
inputs := strings.Split(nextLine(), " ")
var nums []int
for i := 0; i < len(inputs); i++ {
num, _ := strconv.Atoi(inputs[i])
nums = append(nums, num)
}
count := 0
for checkEven(nums) {
count++
for i := 0; i < len(nums); i++ {
nums[i] = nums[i] / 2
}
}
fmt.Println(count)
}
第 4 問: ABC 087 B - Coins (200 点)
素直に全探索ですね
package main
import (
"fmt"
)
func main() {
var (
a, b, c, x, count int
)
fmt.Scan(&a, &b, &c, &x)
for i := 0; i < a+1; i++ {
for j := 0; j < b+1; j++ {
for k := 0; k < c+1; k++ {
if i*500+j*100+k*50 == x {
count++
}
}
}
}
fmt.Println(count)
}
第 5 問: ABC 083 B - Some Sums (200 点)
最初すげぇゴリ押しして解いてました笑
// ABC083B - Some Sums
package main
import (
"fmt"
)
func main() {
var n, a, b, sum int
fmt.Scan(&n, &a, &b)
for i := 1; i < n+1; i++ {
i1 := i % 10
i10 := (i % 100) / 10
i100 := (i % 1000) / 100
i1000 := (i % 10000) / 1000
i10000 := i / 10000 //1≤N≤10^4
if v := i1 + i10 + i100 + i1000 + i10000; a <= v && v <= b {
sum += i
}
}
fmt.Println(sum)
}
後で他の方のエントリみると以下の書き方の方がスッキリしてました
各桁の計算手法は参考になります
package main
import (
"fmt"
)
func sumOfDegit(n int) int {
var sum int
for n > 0 {
sum += n % 10
n /= 10
}
return sum
}
func main() {
var n, a, b, sum int
fmt.Scan(&n, &a, &b)
for i := 1; i < n+1; i++ {
if v := sumOfDegit(i); a <= v && v <= b {
sum += i
}
}
fmt.Println(sum)
}
第 6 問: ABC 088 B - Card Game for Two (200 点)
goでのsortの手間が分かりました笑
sort可能なオブジェクトに変換して・・・という工程を踏むのですね・・・
以下の記事が参考になりました！
package main
import (
"fmt"
"sort"
)
func main() {
var n, alice, bob int
fmt.Scan(&n)
cards := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&cards[i])
}
sort.Sort(sort.Reverse(sort.IntSlice(cards)))
for i := 0; i < n; i += 2 {
alice += cards[i]
if i+1 < n {
bob += cards[i+1]
}
}
fmt.Println(alice - bob)
}
AtCoderではGo1.6が使われているので以下はコンパイルエラーになりますが、Go1.8以降だとこのようにsortの比較関数を実装する方法でもいいみたいです
package main
import (
"fmt"
"sort"
)
func main() {
var n, alice, bob int
fmt.Scan(&n)
cards := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&cards[i])
}
sort.SliceStable(cards, func(i, j int) bool {
if cards[i] > cards[j] {
return true
}
return false
})
for i := 0; i < n; i += 2 {
alice += cards[i]
if i+1 < n {
bob += cards[i+1]
}
}
fmt.Println(alice - bob)
}
第 7 問: ABC 085 B - Kagami Mochi (200 点)
降順sortして大きさが同じでなければ取っていく方針でいいんじゃないかと思って解いてみました
元のエントリを参考にすると連想配列使うやり方がテンプレみたいですね
package main
import (
"fmt"
"sort"
)
func main() {
var n int
fmt.Scan(&n)
mochi := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&mochi[i])
}
sort.Sort(sort.Reverse(sort.IntSlice(mochi)))
count := 1
for i := 1; i < n; i++ {
if mochi[i] == mochi[i-1] {
continue
}
count++
}
fmt.Println(count)
}
連想配列使うver
package main
import (
"fmt"
)
func main() {
var n, mochi int
fmt.Scan(&n)
m := make(map[int]int)
for i := 0; i < n; i++ {
fmt.Scan(&mochi)
m[mochi]++
}
fmt.Println(len(m))
}
第 8 問: ABC 085 C - Otoshidama (300 点)
kまでループしてしまうと実行時間が間に合わない可能性があるので、i+j+k=n の制約を使いましょう
package main
import (
"fmt"
)
func main() {
var n, y int
fmt.Scan(&n, &y)
for i := 0; i <= n; i++ {
for j := 0; j <= (n - i); j++ {
k := n - i - j
if i*10000+j*5000+k*1000 == y {
fmt.Println(i, j, k)
return
}
}
}
fmt.Println(-1, -1, -1)
}
第 9 問: ABC 049 C - Daydream (300 点)
greedyに解くこともできるみたいですが、dfsでやってみました。
↓の部分書いてないために、スライスの範囲外参照エラー出て死ぬほど悩みました笑
if len(s) < len(d[i]) {
continue
}
goでは文字列を逆順にするのは自分で実装するんですね・・・
以下がすごく参考になります！
runeって何？な方は以下も
package main
import (
"fmt"
)
func checkSubstr(s string, d []string) bool {
for i := 0; i < len(d); i++ {
//s[0:len(d[i])]のエラーチェック
if len(s) < len(d[i]) {
continue
}
if s[0:len(d[i])] == d[i] {
if len(s) == len(d[i]) {
return true
}
return checkSubstr(s[len(d[i]):], d)
}
}
return false
}
func reverse(s string) string {
rs := []rune(s)
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
rs[i], rs[j] = rs[j], rs[i]
}
return string(rs)
}
func main() {
var s string
fmt.Scan(&s)
d := []string{"maerd", "remaerd", "esare", "resare"}
s = reverse(s)
if checkSubstr(s, d) {
fmt.Println("YES")
} else {
fmt.Println("NO")
}
}
第 10 問: ABC 086 C - Traveling (300 点)
dfsで書こうとして挫折・・・！
パリティという考え方を使えばラクに解けるそうです。
package main
import (
"fmt"
"math"
)
func main() {
var n, t1, t2 int
var x1, y1, x2, y2 float64
fmt.Scan(&n)
for i := 0; i < n; i++ {
fmt.Scan(&t2, &x2, &y2)
dt := t2 - t1
dist := math.Abs(x2-x1) + math.Abs(y2-y1)
if dt < int(dist) || int(dist)%2 != dt%2 {
fmt.Println("No")
return
}
x1, y1, t1 = x2, y2, t2
}
fmt.Println("Yes")
}
やってみて
- 標準ライブラリがシンプルなので、Goで解くのは結構難易度高め笑
- 大学で最初に触ったC言語の懐かしい記憶が蘇ったｗ