AtCoder 過去問精選 10 問 をGoでやってみた

[A Tour of Go](https://go-tour-jp.appspot.com/moretypes/6)でGoを勉強して、ちょっと手を動かすかと思ったら、有志の方の素晴らしい教材があったので、やってみることに。
問題の詳しい解説は元のエントリが詳しいので是非見てみてください！
[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita](https://qiita.com/drken/items/fd4e5e3630d0f5859067#5-%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-10-%E5%95%8F)

※後でよく考えたら二番煎じかと思って調べてみたら、すでに素敵なエントリがありました笑
[AtCoder に登録したら解くべき精選過去問 10 問を Go で解いてみた - Qiita](https://qiita.com/kakko_hatena/items/8969ddbf432bdd520fc4#%E7%AC%AC-5-%E5%95%8F-abc-083-b---some-sums-200-%E7%82%B9)
とはいえ解き方が違う問題もあるので、置いておきますね

## 第 1 問:  [ABC 086 A - Product](https://beta.atcoder.jp/contests/abc086/tasks/abc086_a) (100 点)
最近PHPとかRuby書いてたので、それに比べるとgoの標準入出力難しいｗ
[※`fmt.Scan`は改行だけでなく空白も区切るので注意](https://qiita.com/koyo-miyamura/items/8766350641287d0a1f2c)

ちなみにGoの標準入力は以下が最高に詳しいです！

* [Go 言語で標準入力から読み込む競技プログラミングのアレ --- 改訂第二版 - Qiita](https://qiita.com/tnoda_/items/b503a72eac82862d30c6)

```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](https://beta.atcoder.jp/contests/abc081/tasks/abc081_a) (100 点)
for使わなくても解けるのですが、普通にfor使いましたｗ

```go
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](https://beta.atcoder.jp/contests/abc081/tasks/abc081_b) (200 点)
素直に解くとこんな感じ？

```go
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

```go
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](https://beta.atcoder.jp/contests/abc087/tasks/abc087_b) (200 点)
素直に全探索ですね

```go
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](https://beta.atcoder.jp/contests/abc083/tasks/abc083_b) (200 点)
最初すげぇゴリ押しして解いてました笑

```go
// 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)
}
```

後で他の方のエントリみると以下の書き方の方がスッキリしてました
各桁の計算手法は参考になります

```go
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](https://beta.atcoder.jp/contests/abc088/tasks/abc088_b) (200 点)
goでのsortの手間が分かりました笑
sort可能なオブジェクトに変換して・・・という工程を踏むのですね・・・

以下の記事が参考になりました！

* [Goのsortパッケージを少し調べた - 電波ビーチ](http://or3.hatenablog.com/entry/2018/01/15/212029)

```go
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の比較関数を実装する方法でもいいみたいです

```go
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](https://beta.atcoder.jp/contests/abc085/tasks/abc085_b) (200 点)
降順sortして大きさが同じでなければ取っていく方針でいいんじゃないかと思って解いてみました
元のエントリを参考にすると連想配列使うやり方がテンプレみたいですね

```go
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

```go
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](https://beta.atcoder.jp/contests/abc085/tasks/abc085_c) (300 点)
kまでループしてしまうと実行時間が間に合わない可能性があるので、i+j+k=n の制約を使いましょう

```go
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](https://beta.atcoder.jp/contests/abc049/tasks/arc065_a) (300 点)

greedyに解くこともできるみたいですが、dfsでやってみました。
↓の部分書いてないために、スライスの範囲外参照エラー出て死ぬほど悩みました笑

```go
        if len(s) < len(d[i]) {
            continue
        }
```

goでは文字列を逆順にするのは自分で実装するんですね・・・
以下がすごく参考になります！

* [Go言語で文字列を逆順に並び替える - Misc Notes](http://y0m0r.hateblo.jp/entry/20131008/1381244919)

runeって何？な方は以下も

* [はじめての Go 言語 (on Windows) その4 - Qiita](https://qiita.com/spiegel-im-spiegel/items/556166b6631c0369754f)


```go
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](https://beta.atcoder.jp/contests/abc086/tasks/arc089_a) (300 点)
dfsで書こうとして挫折・・・！
パリティという考え方を使えばラクに解けるそうです。

* [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita](https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-10-%E5%95%8F--abc-086-c---traveling-300-%E7%82%B9)

```go
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言語の懐かしい記憶が蘇ったｗ