AtCoder 過去問精選10問 をGo言語で解いてみた

はじめに

何番煎じかわかりませんが、Go言語の基本文法を練習するのによさそうだったので、AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～を解いてみました。
普段はPythonしか書いていないので、書き方の違いにも軽く触れてみました。

実際に解いてみる場合は、AtCoder Beginners Selectionに問題がまとめられているので便利です。

問題

0. PracticeA - Welcome to AtCoder

標準入出力の練習です。
標準出力は特に問題ないですが、標準入力については、先に変数を宣言してから、ポインタを使って値を更新するような形になります。

ひとまずは、fmt.Scan()とfmt.Println()が使えれば問題ないと思います。
fmt.Scan()は標準入力をスペースだけでなく改行でも区切るので注意しましょう。

解答例

package main

import "fmt"

func main() {
	var (
		a, b, c int
		s       string
	)
	fmt.Scan(&a, &b, &c, &s)

	fmt.Println(a+b+c, s)
}

1. ABC086A - Product

条件分岐（if文）の練習です。
また、$a \times b$ が偶数になるのは、$a, b$ のいずれかが偶数のときです。

解答例

package main
 
import "fmt"
 
func main() {
	var a, b int
	fmt.Scan(&a, &b)

	if a%2 == 0 || b%2 == 0 {
		fmt.Println("Even")
	} else {
		fmt.Println("Odd")
	}
}

2. ABC081A - Placing Marbles

各桁は0か1しか取らないので、それぞれが1と等しいか比較すればよいです。
比較回数が3回で固定のため、for文を使わなくても十分いけます。

ただし、Go言語では文字列からstring[index]の形で1文字だけ抜き出すと文字列ではなくバイトになるため、stringの"1"ではなくruneの'1'でないと正しく比較できないことに注意してください。

解答例

package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)

	ans := 0
	if s[0] == '1' {
		ans++
	}
	if s[1] == '1' {
		ans++
	}
	if s[2] == '1' {
		ans++
	}

	fmt.Println(ans)
}

別解

以下のようにstrconv.Atoi()を使用して数値型に変換する方法もあります。数字が0から9までの値を取る場合などは、条件式を10個書くのは面倒なのでこちらの方がよいでしょう。
ここで、strconv.Atoi()は2つ目の戻り値としてエラーを返しますが、今回は使わないので_で受けておきましょう。

また、GoではPythonとは違ってint()で文字列を整数に変換することはできないので注意しましょう。

package main

import (
    "fmt"
    "strconv"
)

func main() {
    var s string
    fmt.Scan(&s)

	ans := 0
	tmp, _ := strconv.Atoi(string(s[0]))
	ans += tmp
	tmp, _ = strconv.Atoi(string(s[1]))
	ans += tmp
	tmp, _ = strconv.Atoi(string(s[2]))
	ans += tmp

    fmt.Println(ans)
}

3. ABC081B - Shift only

2で割り切れない数字が出てくるまで繰り返し割ります。繰り返し回数がわからないのでfor文の出番です。
Goにはwhile文やfor each文がありませんが、for文で代用することが可能です。

また、ここでは数値の配列を管理する必要があるので、スライスを使用してみます。
スライスはmake()を使って生成します。

解答例

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	nums := make([]int, n)
	// Pythonの for i in range(n): に相当
	for i := 0; i < n; i++ {
		fmt.Scan(&nums[i])
	}

	var ans int
	ok := true
	// Pythonの while ok: に相当
	for ok {
		// Pythonの for i, num in enumerate(nums): に相当
		for i, num := range nums {
			if num%2 != 0 {
				ok = false
				break
			}
			nums[i] /= 2
		}
		if ok {
			ans++
		}
	}

	fmt.Println(ans)
}

4. ABC087B - Coins

多重ループの問題です。
for文を3つネストさせれば簡単に解ける問題ですが、1つ減らして計算量を削減しています。

また、Goでは、if文を書くときに条件式の前に変数を宣言することができます。ここで宣言した変数はスコープがif文の中に制限されるため、条件式の中で使いたいが、if文の外では使わない変数を宣言するのに便利です。

解答例

package main

import (
	"fmt"
)

func main() {
	var a, b, c, x, ans int
	fmt.Scan(&a, &b, &c, &x)

	for i := 0; i <= a; i++ {
		for j := 0; j <= b; j++ {
			if k := (x - 500*i - 100*j) / 50; 0 <= k && k <= c {
				ans++
			}
		}
	}

	fmt.Println(ans)
}

5. ABC083B - Some Sums

ポイントは10進数の整数の取り扱いです。
「10で割った余りを取り出す」→「10で割る」を繰り返せば各桁の値を取り出すことができます。

今回は、この処理をsumOfDigits()関数として定義しました。
Goでは、戻り値の型を指定するときに、変数名も併せて定義しておくことができます。この場合、関数内での変数宣言を省略できます。また、returnの対象を明示しない場合、定義しておいた変数をreturnします。

解答例

package main
 
import (
	"fmt"
)
 
func sumOfDigits(n int) (r int) {
	for n > 0 {
		r += n % 10
		n /= 10
	}
	return
}
 
func main() {
	var n, a, b, ans int
	fmt.Scan(&n, &a, &b)
 
	for i := 1; i <= n; i++ {
		if s := sumOfDigits(i); a <= s && s <= b {
			ans += i
		}
	}
 
	fmt.Println(ans)
}

6. ABC088B - Card Game for Two

ソートの問題です。
Goでは、ソートにはsortパッケージを使用します。
int型のスライスをソートする場合、sort.Ints(slice)またはsort.Sort(sort.IntSlice(n))とします。
降順にソートしたい場合は、sort.Sort(sort.Reverse(sort.IntSlice(n)))とします。

降順ソートさえできてしまえば、後は貪欲法でAliceとBobに交互に得点を割り振ればOKです。

解答例

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	nums := make([]int, n)
	for i := range nums {
		fmt.Scan(&nums[i])
	}

	var alice, bob int
	sort.Sort(sort.Reverse(sort.IntSlice(nums)))
	for i, num := range nums {
		if i%2 == 0 {
			alice += num
		} else {
			bob += num
		}
	}
	fmt.Println(alice - bob)
}

7. ABC085B - Kagami Mochi

与えられた餅の直径のユニークな値を出せばよいです。

Pythonであればset型を使えば一発でしたが、Goには集合を表す型はないのでmap型で代用します。
Goのmap型は、スライスと同様にmakeで生成します。

解答例

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	m := make(map[int]bool)
	for i := 0; i < n; i++ {
		var d int
		fmt.Scan(&d)
		m[d] = true
	}

	fmt.Println(len(m))
}

8. ABC085C - Otoshidama

4. と似た問題ですが、3重ループにすると時間が厳しいので2重ループで解きます。
文法的には特筆すべき点はありません。

解答例

package main

import "fmt"

func main() {
	var n, y int
	fmt.Scan(&n, &y)

	for i := 0; i <= n; i++ {
		if i*10000 > y {
			break
		}
		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. ABC049C - 白昼夢

いろいろやり方はありますが、正規表現でやるのが簡単かと思います。
Go言語ではregexpパッケージを使います。
※ どうやら、Go言語の正規表現はあまり処理が早くないらしいです。

解答例

package main

import (
	"fmt"
	"regexp"
)

func main() {
	var s string
	fmt.Scan(&s)

	r := regexp.MustCompile(`^(dream(er)?|erase(r)?)*$`)
	if r.MatchString(s) {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}

10. ABC086C - Traveling

$t_0 = x_0 = y_0 = 0, ~ dt_i = dt_{i+1} - dt_i, ~ dx_i = |x_{i+1} - x_i|, ~ dy_i = |y_{i+1} - y_i|$ とすると、
旅行プランを実行できるのは、任意の $i ~ (0 \leq i < N)$ に対して、以下の2条件をみたすときです。

• $dx_i + dy_i \leq dt_i$
• $dx_i + dy_i \equiv dt_i \pmod 2$

絶対値の計算はmath.Abs()がありますが、int型の引数で使いたいので今回は自作しました。

解答例

package main

import (
	"fmt"
)

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func main() {
	var n int
	fmt.Scan(&n)
	t := make([]int, n+1)
	x := make([]int, n+1)
	y := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&t[i], &x[i], &y[i])
	}

	ans := "Yes"
	for i := 0; i < n; i++ {
		dt := t[i+1] - t[i]
		dxy := abs(x[i+1]-x[i]) + abs(y[i+1]-y[i])
		if dt < dxy || dt%2 != dxy%2 {
			ans = "No"
			break
		}
	}

    fmt.Println(ans)
}

参考

• AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
  • 元ネタです。
• AtCoder Beginners Selection
  • 今回の問題がコンテスト形式でまとまっているので便利。
• A Tour of Go
  • Goの基本文法の学習にどうぞ。

まとめ

普段はずっとPythonで書いているので、困惑する部分もありましたがよい勉強になりました。
deferやpanic, goなど、競技プログラミングでは使わなそうな機能については別で勉強したいと思います。