ライブラリを作ってみる

あまり言及されることがないのですが、競技プログラミングにはライブラリを作る楽しさがあると思っています。

競技プログラミングでは様々なデータ構造を駆使すると問題を解きやすくなるので、有用なデータ構造を様々な言語で実装してみると言語ごとの特性が感じられて面白いです。

たとえば、素集合データ構造(disjoint set union structure) というデータ構造があります。
簡単に言うと、**「データの集合を連結したりそれが同じグループかどうかの判定を高速に求められるデータ構造」**です。

コンテストで利用したわけではない(普段は別の言語を使用しています)のですが、 Go でライブラリを作ってみましたのでその紹介をします。

AtCoder 公式の AC Library の実装を元に進めます。
この実装はライセンスが CC0 のため自由に使うことができます。

Go 版の DSU

長いので折りたたみます

package main

import (
	"fmt"
)

func main() {

	d := NewDsu(8)
	d.Merge(1, 2)
	d.Merge(6, 2)
	d.Merge(5, 0)

	fmt.Println(d.Same(1, 6))
	fmt.Println(d.Same(1, 5))
	fmt.Println(d.Groups())

}

type Dsu struct {
	parentOrSize []int
}

func NewDsu(n int) *Dsu {
	parentOrSize := make([]int, 0, n)
	for i := 0; i < n; i++ {
		parentOrSize = append(parentOrSize, -1)
	}
	return &Dsu{
		parentOrSize: parentOrSize,
	}
}

func (d *Dsu) Leader(a int) int {
	if !(0 <= a && a < len(d.parentOrSize)) {
		panic("a is invalid")
	}
	if d.parentOrSize[a] < 0 {
		return a
	}
	d.parentOrSize[a] = d.Leader(d.parentOrSize[a])
	return d.parentOrSize[a]
}

func (d *Dsu) Merge(a int, b int) int {
	if !(0 <= a && a < len(d.parentOrSize)) {
		panic("a is invalid")
	}
	if !(0 <= b && b < len(d.parentOrSize)) {
		panic("b is invalid")
	}

	x := d.Leader(a)
	y := d.Leader(b)

	if x == y {
		return x
	}
	if -d.parentOrSize[x] < -d.parentOrSize[y] {
		tmp := y
		y = x
		x = tmp
	}
	d.parentOrSize[x] += d.parentOrSize[y]
	d.parentOrSize[y] = x
	return x
}

func (d *Dsu) Same(a int, b int) bool {
	if !(0 <= a && a < len(d.parentOrSize)) {
		panic("a is invalid")
	}
	if !(0 <= b && b < len(d.parentOrSize)) {
		panic("b is invalid")
	}

	return d.Leader(a) == d.Leader(b)
}

func (d *Dsu) Size(a int) int {
	if !(0 <= a && a < len(d.parentOrSize)) {
		panic("a is invalid")
	}
	return -d.parentOrSize[d.Leader(a)]
}

func (d *Dsu) Groups() [][]int {
	leaderBuf := make([]int, 0, len(d.parentOrSize))
	groupSize := make([]int, len(d.parentOrSize))

	for i := 0; i < len(d.parentOrSize); i++ {
		leaderBuf = append(leaderBuf, d.Leader(i))
		groupSize[leaderBuf[i]]++
	}

	r := make([][]int, len(d.parentOrSize))
	for i := 0; i < len(d.parentOrSize); i++ {
		r[i] = make([]int, 0, groupSize[i])
	}
	for i := 0; i < len(d.parentOrSize); i++ {
		r[leaderBuf[i]] = append(r[leaderBuf[i]], i)
	}

	r2 := make([][]int, 0, len(d.parentOrSize))
	for _, v := range r {
		if len(v) > 0 {
			r2 = append(r2, v)
		}
	}

	return r2
}

命名規則は言語に合わせて変えてしまいます。

Go は必要なら各々で用意すべしというスタンスのため、コレクション操作関数はあまり用意されていません。
そのため、 Groups() の最後のフィルター処理はロジックを直接実装しています。

他の人の実装を見る

いろいろな言語での実装が見られるので他の人の実装を見るのも良いです。

AC Library は C++ で実装されているので、それを翻訳しなければなりません。

テンプレートの再現などにおいて、各言語への移植方法の工夫が見られて面白いです。

余談

競技プログラミングが役に立つかどうかはよく議題にあがるのですが、個人的にはあまり重視していません。

役立つかどうかは気にしないで楽しいからやっていたりします。

「知っていると役立つこともあるかもしれないなあ」くらいのスタンスが良いのではないかと思っています。

それでは、皆様もよい競技プログラミングライフを！

朝日新聞社では、技術職の中途採用を強化しています。
ご興味のある方は下記リンクから希望職種の募集ページに進んでください。
皆様からのご応募、お待ちしております！