Go言語で最大公約数を求める（ユークリッドの互除法）
Aru
Aru's テクログ（Aruaru0）
AtCoderで使えるGo言語のSortedSetの代替ライブラリ（GoDSのRedBlackTree）
Aru
Go言語でAtCoderにチャレンジしている人は少ないかもしれませんが、Go言語を使っていて困るのはSortedSetがないことです。C++のsetを想定して作成された問題の場合、毎回実装で悩みます。ここでは、GoDSのRedBlackTreeについて紹介します
GoDSとは
GoDSは、Go言語用のデータ構造ライブラリです（github)。色々な便利なデータ構造が用意されています。
このライブラリですが、実はimportするだけでAtCoderで使うことができます（2026年2月現在）。
ここでは、このライブラリにあるRedBlackTree（赤黒木）をSortedSetの代わりに使う方法については、実際のAtCoderの問題を例に紹介します。
GoSTLをつかっても同じようにできますが、ここではこのライブラリの使い方を解説します
あわせて読みたい
AtCoderで使えるC++STLライクなライブラリ「GoSTL」を紹介
RedBlackTree（赤黒木）
赤黒木（Red-Black Tree)は、「自動でバランス調整する二分探索木」です
特徴は以下の通りです。
１．検索・挿入・削除が常に速い
- 普通の二分探索木は、データが順番に並んでいると「ただの長いリスト」になってしまい遅くなります。
- 赤黒木はノードに「赤」か「黒」の色を塗り、特定のルール（色が連続しない等）を守ることで、木が極端に縦長になるのを防ぎます。結果、どんなデータが入ってきても
𝑂(log𝑛) の速度を維持します。
２．データが常にソートされている
- ハッシュテーブル（Goの標準
map）と違い、中のデータが常に並んでいます。 - そのため、「最小値・最大値をすぐ出す」「100以上200以下の要素を全部出す」といった範囲検索が得意です。
３．「バランス調整」のコスパが良い
- 同じ平衡二分木である「AVL木」に比べると、回転（木の組み換え）の回数が少なく済む傾向があり、データの挿入や削除が多いシステムに向いています。
赤黒木は平衡二分木の一種です
これを使うと、SortedSetを使う問題を、Go言語でも簡単に実装できます
ライブラリの説明は以下のページを参考にしてください。
https://pkg.go.dev/github.com/emirpasic/gods/trees/redblacktree
使い方
ライブラリをインポートすれば使えるようになります。具体的には、importに以下の行を挿入します。
import (
: （他のインポート）
rbt "github.com/emirpasic/gods/trees/redblacktree"
)VSCodeなどを使っている場合、どこかでライブラリを使わないとimportがセーブ時に削除されることに注意してください。必ず、コード内にライブラリ呼び出しを記述し、「保存」する必要があります。
go modについて
Goでライブラリを使う場合、上記のライブラリ呼び出しを記述したあとにgo modを呼び出す必要があります。以下のコードを実行してください。
go mod init
go mod tidyこれでローカル環境でもライブラリが利用できるようになります。
AtCoder ABC444E問題を解いてみる
昨日行われたABC444-E問題がちょうどSortedSetを使う問題でしたので、この問題をredblacktreeを使って解いてみます。
この問題の場合、範囲内[a[r]-D: a[r]+D]に値が入っているかどうかをチェックしながら、lを更新するいわゆる「尺取り法」で解くことができる問題です。
値a[r]±Dの範囲の要素があるかどうかをチェックする処理にblack-red treeを使います。
以下、全コードです。
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
rbt "github.com/emirpasic/gods/trees/redblacktree"
)
var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)
func out(x ...interface{}) {
fmt.Fprintln(wr, x...)
}
func getI() int {
sc.Scan()
i, e := strconv.Atoi(sc.Text())
if e != nil {
panic(e)
}
return i
}
func getInts(N int) []int {
ret := make([]int, N)
for i := 0; i < N; i++ {
ret[i] = getI()
}
return ret
}
func main() {
defer wr.Flush()
sc.Split(bufio.ScanWords)
sc.Buffer([]byte{}, math.MaxInt32)
// this template is new version.
// use getI(), getS(), getInts(), getF()
N, D := getI(), getI()
a := getInts(N)
const inf = int(1e15)
s := rbt.NewWithIntComparator()
s.Put(-inf, -inf)
s.Put(inf, inf)
ans, l := 0, 0
for r := 0; r < N; r++ {
for {
left, _ := s.Floor(a[r])
right, _ := s.Ceiling(a[r])
if right.Value.(int)-a[r] >= D && a[r]-left.Value.(int) >= D {
break
}
s.Remove(a[l])
l++
}
s.Put(a[r], a[r])
ans += r - l + 1
}
out(ans)
}
import
ライブラリをインポートする必要があります。
rbt "github.com/emirpasic/gods/trees/redblacktree"初期化
今回はkeyが整数型で良いので、整数型のインスタンスを作成します。
s := rbt.NewWithIntComparator()値の追加、削除
値の追加と削除はPut, Removeを使います。このライブラリでkey, valueを設定できますが、今回は同じ値を設定しています。
s.Remove(a[l])
s.Put(a[r], a[r])前後の値を取得
ここが、C++のsetと異なる部分です。このライブラリでは、FloorとCeilingで値を挟む左右を取得できます。
left, _ := s.Floor(a[r])
right, _ := s.Ceiling(a[r])値の参照
範囲に入っていなければbreakする処理です。Floorの戻り値はNode型でKeyとValueを持ちます。これらの変数はinterface{}型なので、キャストする必要があります。
あわせて読みたい
Go言語のメソッドとinterfaceの使い方、interface{}との違い
if right.Value.(int)-a[r] >= D && a[r]-left.Value.(int) >= D {
break
}まとめ
以上のように、GoDSのRedBlackTreeを使うことで、C++のsetを使うような問題を解くことができます。AtCoderをGo言語でチャレンジしている方はぜひ参考にしてください。
ABOUT ME
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中
