本記事について
本記事では、Go言語1.18で追加されたのGenericsを使って、
最大（Max）・最小（Min）・総和（Sum）を求める関数を作ります。
Genericsを使うメリットとして、
- 引数の型と返り値の型が違うだけで、中身が全く同じ動きをしている関数が1つになる
- 1つの関数のバグが複数個のバグにならなくなる
- 引数に与える値が特定の型に合致しているか、関数が実装されているかどうか判定できる
- 「この関数が実装されてないと動かないよ！」「この型じゃないとダメだよ！」とコードを書いている最中にツールが教えてくれる
- interface{}を引数に取った型スイッチによる分岐が減る
- 関数実装時に持つ「なんか強引な実装だな」というモヤモヤ感がなくなる
という3点があります。
本記事では、競技プログラミングサイトのAtCoderの問題を通して、GoのGenericsを使った簡単な関数を作成します。
AtCoderの言語アップデート
8月にAtCoderの提出言語アップデートが来ました。これにより、AtCoder上ではGo言語は1.20.6となり、C++はC++23となるなど、様々な新機能が使えるようになりました。
（詳しくは、AtCoderの使用できる言語とライブラリの一覧とスプレッドシートを確認していただければと思います）
Go言語は1.18にGenericsが追加されました。
さらに、1.20でComparable等のinterfaceが追加されるなど、Go言語でAtCoderを取り組む上でコード管理が非常に簡単になりました。
本記事では、AtCoderの問題を1つ取り上げ、GoのGenericsを使って解いていこうと思います。
今回取り上げる問題
本記事で取り組む問題はABC063 C問題 Buggedです。
ざっくりとした問題概要はこんな感じです。
長さ$N$の整数列$S = S_1, S_2, ..., S_N$が与えられます。
数列の最大の長さ（$N$の最大値）は$N = 100$で、数列の$i$番目の値を$S_i$とすると、$1 \leq S_i \leq 100$です。
この整数列$S$からいくつか要素を取り除き（取り除かなくても良い）、取り除いた後の総和が10の倍数ではない最大の値はいくつになりますか？
ただし、どのような取り除き方をしても10の倍数となる場合は0としてください。
（例1）
$N = 3, S = 5, 10, 15$のとき、答えは$25$（$5$を取り除けばよい）
（例2）
$N = 3, S = 10, 10, 15$のとき、答えは$35$（何も取り除く必要はない）
解答方針
さて、どのように考えたでしょうか。
個人的に注目したのは、 「どのような取り除き方をしても10の倍数となるなら」という部分です。
この場合、数列の全要素が10の倍数でないと成り立ちません。
逆に考えれば、1つ以上の要素が10の倍数でないなら、何も取らない状態で10の倍数であったとしても、10の倍数でない一番小さい値を取り除いてしまえば良いわけです。
例えば、この場合は全て10の倍数なので、何を取り除いてもダメです。
この場合は8,3,17,2が10の倍数ではないので、2を取り除くことで総和が10の倍数でなくなり、これが最大値になります。（取り除かない場合は60となり、10の倍数です）
このことから、総和が10の倍数なら数列の全要素を見て、10の倍数でない一番小さい値を取り除けば答えとなることが分かります。
実装
考察が終わったので、実装に入ります。
まずはmain関数を実装します。main関数で入力を受け取り、solve関数で問題の解答方法を実装するようにします。（このあたりは好みが別れます）
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
var (
n int
S []int
input = bufio.NewScanner(os.Stdin)
)
// 最初のNを受け取る
fmt.Scan(&n)
// 改行文字区切りで入力を受け取る
for input.Scan() {
// 受け取った文字列を半角空白区切りで分ける
for _, v := range strings.Split(input.Text(), " ") {
// 文字列を数値に変換してSの末尾に追加する
if s, err := strconv.Atoi(v); err == nil {
S = append(S, s)
} else {
fmt.Println("Input Error")
}
}
}
// 解答用の関数に入力を渡して表示する
ans := solve2(n, S)
fmt.Println(ans)
}
次にsolve関数を実装します。
/*
解答用の関数
*/
func solve(n int, S []int) int {
const (
SENTINEL = 101 // 数列Sの最大値が100なので、101を変更したかどうかのフラグとする
)
var (
ans = SumInts(S...)
minNot10 = SENTINEL
)
if ans%10 == 0 {
for _, s := range S {
if s%10 != 0 {
minNot10 = MinInt(minNot10, s)
}
}
if minNot10 == SENTINEL {
ans = 0
} else {
ans -= minNot10
}
}
return ans
}
さてここで、SumIntsとMinIntという２つの関数が出てきました。
これらの関数の挙動はこのようにします。
-
SumInts: int型の可変長引数を取り、総和を返す（何もないなら0） -
MinInt: 2つのint型の値を取り、どちらか小さい方を返す
実装はこのようになります。
/*
int型の数値を引数に、総和を返す
何も与えられない場合は0を返す
*/
func SumInts(values ...int) int {
sum := 0
for _, v := range values {
sum += v
}
return sum
}
/*
2つのint型の値を引数に、小さい方の値を返す
*/
func MinInt(x, y int) int {
if x < y {
return x
} else {
return y
}
}
提出してみる
コードが書けたので提出してみると、正解（AC）となります。
関数に色々な型を受け取れるようにする
正解となったので問題としてはここで終了ですが、少し工夫したいと思います。
今回実装したSumInts関数とMinInt関数はその名の通り、int型の総和を得る、２つの値で小さい方を得るという関数です。
では、もし入力に$10^{18}$、$3.14$といった値が来たらどうしますか？
$10^{18}$は32bit整数では表現できません。$3.14$は浮動小数点なのでfloat32かfloat64で対応しなくてはなりません。
現状の実装だと、各型（int/int64/float64など）で同様の処理を書かなくてはなりません。
例えば、SumIntsをそれぞれの型に合わせるとこうなります。
/*
int型の数値を引数に、総和を返す
何も与えられない場合は0を返す
*/
func SumInts(values ...int) int {
sum := 0
for _, v := range values {
sum += v
}
return sum
}
/*
int64型の数値を引数に、総和を返す
何も与えられない場合は0を返す
*/
func SumInt64s(values ...int64) int64 {
sum := int64(0)
for _, v := range values {
sum += v
}
return sum
}
/*
float64型の数値を引数に、総和を返す
何も与えられない場合は0を返す
*/
func SumFloat64s(values ...float64) float64 {
sum := float64(0)
for _, v := range values {
sum += v
}
return sum
}
コード量が３倍になりました。性能は３倍、可読性は1/9です。 これをMinIntも同様にコピペ実装するのは面倒です。
ここで活躍するのがGenericsです。
Genericsを使って実装する
Genericsを使わない実装は以下の2点が問題だと考えられます。
- 同じ処理を複数の型で実装しなくてはならない
- もし何か1つの関数にミスが発覚した場合、同様の処理を持つ全ての関数が影響範囲になる
Genericsを使うことで、以下のように解決できます。
- 同じ処理は1つの関数で実装出来る
- 関数が１つなので、ミスが発覚した場合は呼び出した関数の処理を変更すれば良い
今回の問題は整数を受け取っているので、全ての整数型に対応するMin/Sum関数を実装します。
整数型を定義する
まずは、「これが整数です」というグループを定義します。
整数は数学で$\mathbb{Z}$で書かれがちです。これはドイツ語で整数を意味する"Zahl"の頭文字です。
そのため、整数型をZahl型として定義します。
Go言語は符号付き整数にint、符号なし整数にuint型があります。
それぞれに8bit、16bit、32bit、64bit用がありますので、全てまとめて「整数」というグループにまとめます。
実装はこんな感じになります。
/*
整数型を定義したinterface
*/
type Zahl interface {
int | int8 | int16 | int32 | int64 | uint | uint8 | uint16 | uint32 | uint64
}
GoのGenericsで型をまとめる場合はinterfaceに型名を書きます。複数の型を許容する場合は|で区切ります。
関数を実装する
整数型を実装できたので、次は整数型を受け取る関数を作成します。
Genericsを使った実装は、Genericsを使わない実装で書いたような形で書くことができ、
関数名と引数の間に、[型の仮の名前 型名]を挟み込めば良いです。引数や返り値の型は型の仮の名前を使えば良いです。
/*
整数型を引数に、総和を返す
*/
func Sum[Z Zahl](values ...Z) Z {
sum := Z(0)
for _, v := range values {
sum += v
}
return sum
}
/*
2つの整数型の値を引数に、小さい方の値を返す
*/
func Min[Z Zahl](x, y Z) Z {
if x < y {
return x
} else {
return y
}
}
これで整数全てに対応したMin / Sum 関数を作ることが出来ました。
先程3倍に増えたコードが1つにまとまり、性能はさらに3倍、可読性も3倍です！
solve関数を作る
再度solve関数を作りましょう。
といっても関数名を変えるだけで良く、変数の型はコンパイル時に解決されるので特に考える必要がありません。
/*
解答用の関数
*/
func solve2(n int, S []int) int {
const (
SENTINEL = 101 // 数列Sの最大値が100なので、101を変更したかどうかのフラグとする
)
var (
ans = Sum(S...)
minNot10 = SENTINEL
)
if ans%10 == 0 {
for _, s := range S {
if s%10 != 0 {
minNot10 = Min(minNot10, s)
}
}
if minNot10 == SENTINEL {
ans = 0
} else {
ans -= minNot10
}
}
return ans
}
提出してみる
Genericsを使って作成した解答コードを作り終えたので、提出してみましょう。
(main関数のsolveもsolve2に変えておいてください)
正解（AC）と出ればOKです。
まとめ
今回はGenericsを使って関数を実装し、AtCoderの問題を使って動作確認をしてみました。
Genericsを使うことで、複数の型で同じ処理を書いていた関数が１つにまとまり、可用性が高まります。
Genericsは今後拡張されると思うので、自分の書くコードにもどんどん取り入れていきたいです。
おまけ
最大を返すMax関数を実装する
Min関数を書いたのにMax関数が無いやん！ということで、Maxも実装します。
Min関数の返り値を逆にする（もしくは不等号を逆にする）だけで良いので簡単です。
/*
2つの整数型の値を引数に、大きい方の値を返す
*/
func Max[Z Zahl](x, y Z) Z {
if x < y {
return y
} else {
return x
}
}
実数型を定義する
今回は整数型としてZahlを定義しましたが、同様に実数も出来ます。
実数は記号で$\mathbb{R}$なので、Realとします。（厳密には実数でないのですが便宜上実数です）
Real型の中にZhal型を入れ込むことができ、Zhal型で対応可能な型がReal型でも対応できるようになります。
/*
実数型を定義したinterface
*/
type Real interface {
Zahl | float32 | float64
}
[Z Zahl]の部分を[R Real]に変更すれば、浮動小数点対応のMin/Max/Sum関数の完成です。
提出例
Go 1.14までの記法で正解した提出はこちらです。
Genericsを使って正解した提出はこちらです。
参考文献