#1077706 (Go) No.3109 Swap members

提出ソース
結果

問題	No.3109 Swap members
ユーザー	gj5752
提出日時	2025-04-20 01:21:19
言語	Go (1.23.4)
結果	AC
実行時間	178 ms / 2,000 ms
コード長	25,145 bytes
コンパイル時間	13,564 ms
コンパイル使用メモリ	236,300 KB
実行使用メモリ	13,256 KB
最終ジャッジ日時	2025-04-20 01:21:38
合計ジャッジ時間	18,503 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 52
権限があれば一括ダウンロードができます
ソースコード

raw source code
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
	// "regexp"
)

var (
	// Scanner は 1 行ずつ読む
	sc = bufio.NewScanner(os.Stdin)
	// 標準出力に書き出す
	wr = bufio.NewWriter(os.Stdout)
)

const (
	mod = 998244353
	// mod = int(1e9 + 7)
	INF = 1 << 62
)

func solve() {
	// START
	n, k := readI2()
	name := make(map[string]int)
	for i := 0; i < n; i++ {
		s := readS()
		name[s] = i
	}
	t := make([]int, n)
	for i := 0; i < n; i++ {
		tn := readS()
		t[i] = name[tn]
	}
	for i := 0; i < n; i++ {
		for j := i; j < n; j += k {
			if (t[j]-i)%k == 0 {
				continue

			} else {
				printN()
				return
			}

		}
	}
	printY()
	// END
}

//

//

// main 関数
func main() {
	// 空白区切りで読む込むように設定
	sc.Split(bufio.ScanWords)
	// 最大読み込み文字数を2*10^5に対応
	// 2*10^6 のバッファを確保
	sc.Buffer(make([]byte, 2000000*1+1), 2000000)
	// 全部書き出す
	defer wr.Flush()

	solve()
}

//////////////////////////////////////
// 標準入出力に関わる関数
//////////////////////////////////////

// 整数の読み込み
func readI() int {
	// 空白区切りで文字列として読み込む
	sc.Scan()
	// Text() メソッドで読み込んだものを取り出す
	// 文字列を整数に変換
	i, _ := strconv.Atoi(sc.Text())
	return i
}

// 整数列の読み込み
func readInts(n int) []int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = readI()
	}
	return arr
}

// [value, index] で整数列の読み込み
func readIntsWithIdx(n int) [][]int {
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, 2)
		arr[i][0], arr[i][1] = readI(), i
	}
	return arr
}

// n*m 2次元整数列の読み込み
func readTwoInts(n int, m int) [][]int {
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, m)
		arr[i] = readInts(m)
	}
	return arr
}

// 2つの長さnの整数列を行ずつ読み込み
func readIntsARow2(n int) ([]int, []int) {
	arr1 := make([]int, n)
	arr2 := make([]int, n)
	for i := 0; i < n; i++ {
		arr1[i], arr2[i] = readI2()
	}
	return arr1, arr2
}

// 3つの長さnの整数列を行ずつ読み込み
func readIntsARow3(n int) ([]int, []int, []int) {
	arr1 := make([]int, n)
	arr2 := make([]int, n)
	arr3 := make([]int, n)
	for i := 0; i < n; i++ {
		arr1[i], arr2[i], arr3[i] = readI3()
	}
	return arr1, arr2, arr3
}

// 4つの長さnの整数列を行ずつ読み込み
func readIntsARow4(n int) ([]int, []int, []int, []int) {
	arr1 := make([]int, n)
	arr2 := make([]int, n)
	arr3 := make([]int, n)
	arr4 := make([]int, n)
	for i := 0; i < n; i++ {
		arr1[i], arr2[i], arr3[i], arr4[i] = readI4()
	}
	return arr1, arr2, arr3, arr4
}

// idx0 を開けて n 個の整数を n+1 要素の整数列へ読み込み
func readInts0(n int) []int {
	arr := make([]int, n+1)
	for i := 1; i <= n; i++ {
		arr[i] = readI()
	}
	return arr
}

func readI2() (int, int)                { return readI(), readI() }
func readI3() (int, int, int)           { return readI(), readI(), readI() }
func readI4() (int, int, int, int)      { return readI(), readI(), readI(), readI() }
func readI5() (int, int, int, int, int) { return readI(), readI(), readI(), readI(), readI() }
func readI6() (int, int, int, int, int, int) {
	return readI(), readI(), readI(), readI(), readI(), readI()
}

func readInts2(n int) ([]int, []int)        { return readInts(n), readInts(n) }
func readInts3(n int) ([]int, []int, []int) { return readInts(n), readInts(n), readInts(n) }
func readInts4(n int) ([]int, []int, []int, []int) {
	return readInts(n), readInts(n), readInts(n), readInts(n)
}

// 文字列の読み込み
func readS() string {
	sc.Scan()
	return sc.Text()
}

// []byte で文字列の読み込み
func readSBytes() []byte {
	sc.Scan()
	return []byte(sc.Text())
}

// 文字列列の読み込み
func readStrings(n int) []string {
	arr := make([]string, n)
	for i := 0; i < n; i++ {
		arr[i] = readS()
	}
	return arr
}

func readS2() (string, string)                 { return readS(), readS() }
func readS3() (string, string, string)         { return readS(), readS(), readS() }
func readS4() (string, string, string, string) { return readS(), readS(), readS(), readS() }
func readS5() (string, string, string, string, string) {
	return readS(), readS(), readS(), readS(), readS()
}

func readSBytes2() ([]byte, []byte)         { return readSBytes(), readSBytes() }
func readSBytes3() ([]byte, []byte, []byte) { return readSBytes(), readSBytes(), readSBytes() }
func readSBytes4() ([]byte, []byte, []byte, []byte) {
	return readSBytes(), readSBytes(), readSBytes(), readSBytes()
}
func readSBytes5() ([]byte, []byte, []byte, []byte, []byte) {
	return readSBytes(), readSBytes(), readSBytes(), readSBytes(), readSBytes()
}

// 外側をxで覆ってh*wのボードを読み込む
func readBoard(h, w int, x byte) [][]byte {
	board := newTwoBytes(h+2, w+2, x)
	for i := 1; i <= h; i++ {
		t := readSBytes()
		for j := 1; j <= w; j++ {
			board[i][j] = t[j-1]
		}
	}
	return board
}

// 改行なしで単体出力
func printB(x ...interface{}) {
	fmt.Fprint(wr, x...)
}

// 最後に改行ありで出力 並列の場合はそのまま[]byteも[]intも出力
func print(x ...interface{}) {
	if len(x) == 1 {
		switch x[0].(type) {
		case []byte:
			fmt.Fprintln(wr, string(x[0].([]byte)))
		case []int:
			printInts(x[0].([]int))
		default:
			fmt.Fprintln(wr, x...)
		}
	} else {
		fmt.Fprintln(wr, x...)
	}
}

// Yesを出力
func printY() {
	fmt.Fprintln(wr, "Yes")
}

// Noを出力
func printN() {
	fmt.Fprintln(wr, "No")
}

// 整数列を空白区切りで出力
func printInts(x []int) {
	for i := 0; i < len(x); i++ {
		fmt.Fprint(wr, x[i])
		fmt.Fprint(wr, " ")
	}
	fmt.Fprintln(wr)
}

// 整数列を改行区切りで出力
func printIntsln(x []int) {
	for i := 0; i < len(x); i++ {
		fmt.Fprintln(wr, x[i])
	}
}

// 文字列列を空白区切りで出力
func printStrings(x []string) {
	for i := 0; i < len(x); i++ {
		fmt.Fprint(wr, x[i])
		fmt.Fprint(wr, " ")
	}
	fmt.Fprintln(wr)
}

// 文字列列を改行区切りで出力
func printStringsln(x []string) {
	for i := 0; i < len(x); i++ {
		fmt.Fprintln(wr, x[i])
	}
}

// []byte を文字列に変換して出力
func printBytes(s []byte) {
	print(string(s))
}

//////////////////////////////////////
// Basinc Functions
//////////////////////////////////////

// min(a, b)
func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

// min(a, b) int64
func min64(a, b int64) int64 {
	if a < b {
		return a
	} else {
		return b
	}
}

// min(a, b) float64
func minFloat(a, b float64) float64 {
	if a < b {
		return a
	} else {
		return b
	}
}

// max(a, b)
func max(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}

// max(a, b) int64
func max64(a, b int64) int64 {
	if a < b {
		return b
	} else {
		return a
	}
}

// min(a, b) float64
func maxFloat(a, b float64) float64 {
	if a < b {
		return b
	} else {
		return a
	}
}

// |a|
func abs(a int) int {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

// |a| int64
func abs64(a int64) int64 {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

// |a| float64
func absFloat(a float64) float64 {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

// p^n
func power(p, n int) int {
	res := 1
	x := p
	for n != 0 {
		if n%2 == 1 {
			res *= x
		}
		n /= 2
		x = x * x
	}
	return res
}

// p^n int64
func power64(p, n int64) int64 {
	res := int64(1)
	x := p
	for n != 0 {
		if n%2 == 1 {
			res *= x
		}
		n /= 2
		x = x * x
	}
	return res
}

// p^n float64
func powerFloat(p float64, n int) float64 {
	res := float64(1)
	x := p
	for n != 0 {
		if n%2 == 1 {
			res *= x
		}
		n /= 2
		x = x * x
	}
	return res
}

// sum a[]
func sumInts(a []int) int {
	res := 0
	for i := range a {
		res += a[i]
	}
	return res
}

// n!
func factorial(n int) int {
	res := 1
	for i := 2; i <= n; i++ {
		res *= i
	}
	return res
}

// prime check
func isPrime(n int) bool {
	if n == 1 {
		return false
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

// 整数列昇順ソート
func sortInts(x []int) {
	sort.Ints(x)
}

// 整数列降順ソート
func sortIntsR(x []int) {
	sort.SliceStable(x, func(i, j int) bool { return x[i] > x[j] })
}

// 整数列 a を昇順にし、その ind で b を並び替える書き換えをする
func sortIntsAscendWith(a []int, b []int) {
	x := make([][2]int, len(a))
	for i := range x {
		x[i] = [2]int{a[i], b[i]}
	}
	sort.SliceStable(x, func(i, j int) bool { return x[i][0] < x[j][0] })
	for i := range x {
		a[i] = x[i][0]
		b[i] = x[i][1]
	}
}

// 整数列 a を降順にし、その ind で b を並び替える書き換えをする
func sortIntsDeascendWith(a []int, b []int) {
	x := make([][2]int, len(a))
	for i := range x {
		x[i] = [2]int{a[i], b[i]}
	}
	sort.SliceStable(x, func(i, j int) bool { return x[i][0] > x[j][0] })
	for i := range x {
		a[i] = x[i][0]
		b[i] = x[i][1]
	}
}

// 整数列を逆順にする
func reverseInts(x []int) {
	y := copyInts(x)
	n := len(x)
	for i := range x {
		x[i] = y[n-1-i]
	}
}

// 文字列を逆順にする
func reverseString(s string) string {
	x := strings.Split(s, "")
	sort.SliceStable(x, func(i, j int) bool { return i > j })
	return strings.Join(x, "")
}

// 文字列を辞書順にソート
func sortString(s string) string {
	x := strings.Split(s, "")
	sort.SliceStable(x, func(i, j int) bool { return x[i] < x[j] })
	return strings.Join(x, "")
}

// []byteを辞書順にソート
func sortBytes(s []byte) {
	sort.SliceStable(s, func(i, j int) bool { return s[i] < s[j] })
}

// []byteを逆順にする
func reverseBytes(s []byte) {
	sort.SliceStable(s, func(i, j int) bool { return i > j })
}

// 辞書的に次の文字列（ない場合はfalse）
func nextPermutationString(s string) (bool, string) {
	// maxi は連続2文字が辞書順にならなくなる一番手前の場所
	// 2167543 なら 6 の位置
	// ここより後はもう増やせない 7543 が最大
	maxi, maxj := 0, 0
	for i := 0; i < len(s)-1; i++ {
		if s[i] < s[i+1] {
			maxi = i
		}
	}
	// maxj は maxi の文字より辞書的に大きいものの一番後ろの場所
	// 2167543 では 7 の位置
	for j := 0; j < len(s); j++ {
		if s[maxi] < s[j] {
			maxj = j
		}
	}
	if maxi == maxj {
		return false, s
	}
	// maxi と maxj を swap する
	// 2176543
	var x string
	if maxi < maxj {
		x = s[:maxi] + s[maxj:maxj+1] + s[maxi+1:maxj] + s[maxi:maxi+1] + s[maxj+1:]
	} else {
		x = s[:maxj] + s[maxi:maxi+1] + s[maxj+1:maxi] + s[maxj:maxj+1] + s[maxi+1:]
	}
	// もとの maxi の位置より後ろを逆にする
	// 2173456
	return true, x[:maxi+1] + reverseString(x[maxi+1:])
}

// []byte を辞書的に次の文字列に書き換える（ない場合はfalse）
func nextPermutationBytes(s []byte) bool {
	maxi, maxj := 0, 0
	for i := 0; i < len(s)-1; i++ {
		if s[i] < s[i+1] {
			maxi = i
		}
	}
	for j := 0; j < len(s); j++ {
		if s[maxi] < s[j] {
			maxj = j
		}
	}
	if maxi == maxj {
		return false
	}
	s[maxi], s[maxj] = s[maxj], s[maxi]
	reverseBytes(s[maxi+1:])
	return true
}

// "123...n" という文字列を返す
func numStringFrom1(n int) string {
	str := ""
	for i := 1; i <= n; i++ {
		str += strconv.Itoa(i)
	}
	return str
}

// "012...n" という文字列を返す
func numStringFrom0(n int) string {
	str := ""
	for i := 0; i <= n; i++ {
		str += strconv.Itoa(i)
	}
	return str
}

// 文字列としての数字のi文字目の数字を返す（iは0から）
func numOf(s string, i int) int {
	res, _ := strconv.Atoi(s[i : i+1])
	return res
}

// 0 ~ 9 の文字としての byte 1文字を int に変換
func byteToInt(b byte) int {
	return int(b) - 48
}

// 0 ~ 9 の int を byte 1文字に変換
func intToByte(i int) byte {
	return byte(i) + 48
}

// 整数列を init で初期化して作成
func newInts(size int, init int) []int {
	arr := make([]int, size)
	if init == 0 {
		return make([]int, size)
	}
	for i := range arr {
		arr[i] = init
	}
	return arr
}

func newInts2(size int, init int) ([]int, []int) { return newInts(size, init), newInts(size, init) }
func newInts3(size int, init int) ([]int, []int, []int) {
	return newInts(size, init), newInts(size, init), newInts(size, init)
}
func newInts4(size int, init int) ([]int, []int, []int, []int) {
	return newInts(size, init), newInts(size, init), newInts(size, init), newInts(size, init)
}
func newInts5(size int, init int) ([]int, []int, []int, []int, []int) {
	return newInts(size, init), newInts(size, init), newInts(size, init), newInts(size, init), newInts(size, init)
}

// n*m 2次元整数列を init で初期化して作成
func newTwoInts(n int, m int, init int) [][]int {
	arr := make([][]int, n)
	if init == 0 {
		for i := range arr {
			arr[i] = make([]int, m)
		}
	} else {
		for i := range arr {
			arr[i] = newInts(m, init)
		}
	}
	return arr
}

// 整数列のコピー
func copyInts(x []int) []int {
	res := make([]int, len(x))
	copy(res, x)
	return res
}

// 2次元整数列のコピー
func copyTwoInts(x [][]int) [][]int {
	n := len(x)
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, len(x[i]))
		copy(res[i], x[i])
	}
	return res
}

// 初期値が init で n 文字の []byte を作成
func newBytes(n int, init byte) []byte {
	arr := make([]byte, n)
	for i := range arr {
		arr[i] = init
	}
	return arr
}

// 初期値 init で h * w の [][]byte を作成
func newTwoBytes(h, w int, init byte) [][]byte {
	arr := make([][]byte, h)
	for i := 0; i < h; i++ {
		arr[i] = newBytes(w, init)
	}
	return arr
}

// []byteのコピー
func copyBytes(x []byte) []byte {
	res := make([]byte, len(x))
	copy(res, x)
	return res
}

// 2次元[]byteのコピー
func copyTwoBytes(x [][]byte) [][]byte {
	n := len(x)
	res := make([][]byte, n)
	for i := 0; i < n; i++ {
		res[i] = make([]byte, len(x[i]))
		copy(res[i], x[i])
	}
	return res
}

//////////////////////////////////////
// mod
//////////////////////////////////////

// a + b mod
func modAdd(a, b int) int {
	res := (a + b) % mod
	if res < 0 {
		res += mod
	}
	return res
}

// a - b mod
func modSub(a, b int) int {
	res := (a - b) % mod
	if res < 0 {
		res += mod
	}
	return res
}

// a * b mod
func modMul(a, b int) int {
	a %= mod
	b %= mod
	res := (a * b) % mod
	if res < 0 {
		res += mod
	}
	return res
}

// p^n mod
func modPower(p, n int) int {
	res := 1
	x := p % mod
	for n != 0 {
		if n%2 == 1 {
			res *= x
			res %= mod
		}
		n /= 2
		x = (x * x) % mod
	}
	return res
}

// a^(-1) mod
func modInv(a int) int {
	b, u, v := mod, 1, 0
	for b != 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= mod
	if u < 0 {
		u += mod
	}
	return u
}

// a / b mod
func modDiv(a, b int) int {
	a %= mod
	res := a * modInv(b)
	res %= mod
	return res
}

// a! mod
func modFact(a int) int {
	res := a
	for a > 1 {
		a--
		res = modMul(res, a)
	}
	if res < 0 {
		res += mod
	}
	return res
}

// nPr mod
func modP(n, r int) int {
	res := n
	for r > 1 {
		n--
		r--
		res = modMul(res, n)
	}
	if res < 0 {
		res += mod
	}
	return res
}

// nCr mod
func modC(n, r int) int {
	return modDiv(modP(n, r), modFact(r))
}

//////////////////////////////////////////////////////////////
// Pos
//////////////////////////////////////////////////////////////

// 2次元座標
type Pos struct {
	x int
	y int
}

// Pos の読み込み
func readPos() Pos {
	return Pos{readI(), readI()}
}

func readPos2() (Pos, Pos) { return Pos{readI(), readI()}, Pos{readI(), readI()} }

// Pos 列を読み込み
func readPoss(n int) []Pos {
	arr := make([]Pos, n)
	for i := 0; i < n; i++ {
		arr[i] = readPos()
	}
	return arr
}

// 長さ
func length(p Pos) float64 {
	t := p.x*p.x + p.y*p.y
	return math.Sqrt(float64(t))
}

// ユークリッド距離
func distance(p, q Pos) float64 {
	t := power(p.x-q.x, 2) + power(p.y-q.y, 2)
	return math.Sqrt(float64(t))
}

//////////////////////////////////////////////////////////////
// Self-Balancing Binary Search Tree 平衡二分探索木 AVL木
//////////////////////////////////////////////////////////////

type AVLNode struct {
	key    int
	height int
	left   *AVLNode
	right  *AVLNode
}

// 左の子を取得

func (n *AVLNode) getLeft() *AVLNode {
	if n == nil {
		return nil
	}
	return n.left
}

// 右の子を取得

func (n *AVLNode) getRight() *AVLNode {
	if n == nil {
		return nil
	}
	return n.right
}

// 高さを取得

// nilなら0
func (n *AVLNode) getHeight() int {
	if n == nil {
		return 0
	}
	return n.height
}

// keyを取得

// nilなら-1
func (n *AVLNode) getKey() int {
	if n == nil {
		return -1
	}
	return n.key
}

// 高さを更新

func (n *AVLNode) updateHeight() {
	if n == nil {
		return
	}
	n.height = 1 + max(n.left.getHeight(), n.right.getHeight())
}

// 左回転：nの右の子が新たな根となる
// 右の子の左の子はnの右の子に新しくなる

func (n *AVLNode) rotateLeft() *AVLNode {
	if n.getRight() == nil {
		return n
	}
	newRoot := n.getRight()
	n.right = newRoot.getLeft()
	newRoot.left = n

	newRoot.updateHeight()
	n.updateHeight()
	return newRoot
}

// 右回転：nの左の子が新たな根となる
// 左の子の右の子はnの左の子に新しくなる

func (n *AVLNode) rotateRight() *AVLNode {
	if n.getLeft() == nil {
		return n
	}
	newRoot := n.getLeft()
	n.left = newRoot.getRight()
	newRoot.right = n

	newRoot.updateHeight()
	n.updateHeight()
	return newRoot
}

// バランスを整える
// 平衡係数と子のバランスによって回転や二重回転を行う

func (n *AVLNode) rebalance() *AVLNode {
	if n == nil {
		return n
	}
	n.updateHeight()

	// 平衡係数
	balanceFactor := n.left.getHeight() - n.right.getHeight()
	// 右の子の方が重い
	if balanceFactor == -2 {
		// 右の子について、左の方が重ければ二重回転が必要
		// 一旦右の子を右回転しておく
		if n.right.left.getHeight() > n.right.right.getHeight() {
			n.right = n.right.rotateRight()
		}
		return n.rotateLeft()
	} else if balanceFactor == 2 {
		if n.left.right.getHeight() > n.left.left.getHeight() {
			n.left = n.left.rotateLeft()
		}
		return n.rotateRight()
	}
	return n
}

// その部分木内でkeyを挿入
// keyがすでにあればそのノード

func (n *AVLNode) insert(key int) *AVLNode {
	if n == nil {
		return &AVLNode{key, 1, nil, nil}
	}
	if key < n.key {
		n.left = n.left.insert(key)
	} else if key > n.key {
		n.right = n.right.insert(key)
	} else {
		return n
	}
	return n.rebalance()
}

// その部分木内でkeyを削除
// keyがなければnil

func (n *AVLNode) remove(key int) *AVLNode {
	if n == nil {
		return nil
	}
	if key < n.key {
		n.left = n.left.remove(key)
	} else if key > n.key {
		n.right = n.right.remove(key)
	} else {
		if n.left != nil && n.right != nil {
			// 根を削除するときは右側から最小をさがしてきて
			// 新たな根とする
			newRoot := n.right.minNode()
			n.key = newRoot.key
			n.right = n.right.remove(newRoot.key)
		} else if n.left != nil {
			n = n.left
		} else if n.right != nil {
			n = n.right
		} else {
			n = nil
			return n
		}
	}
	return n.rebalance()
}

// その部分木内でkeyを探索
// keyがなければnil

func (n *AVLNode) search(key int) *AVLNode {
	if n == nil {
		return nil
	}
	if key < n.key {
		return n.left.search(key)
	} else if key > n.key {
		return n.right.search(key)
	} else {
		return n
	}
}

// その部分木内でkeyより大きい最小のノード
// なければnil
// keyと一致するノードがあればそれを返す

func (n *AVLNode) lowerBound(key int) *AVLNode {
	if n == nil {
		return nil
	}
	if key < n.key {
		// keyが注目ノード未満なら左の部分木を調べれば良い
		// そこになければn自身がlowerbound (左部分木のmax<keyのため)
		res := n.left.lowerBound(key)
		if res != nil {
			return res
		} else {
			return n
		}
	} else if key > n.key {
		// keyが注目モードより大きければ右を調べるのみ
		return n.right.lowerBound(key)
	} else {
		return n
	}
}

// その部分木内でkeyより小さい最大のノード
// なければnil
// keyと一致するノードがあればそれを返す

func (n *AVLNode) upperBound(key int) *AVLNode {
	if n == nil {
		return nil
	}
	// lowerBoundと逆を行う
	if key > n.key {
		res := n.right.upperBound(key)
		if res != nil {
			return res
		} else {
			return n
		}
	} else if key < n.key {
		return n.left.upperBound(key)
	} else {
		return n
	}
}

// その部分木内で最小ノード

func (n *AVLNode) minNode() *AVLNode {
	if n == nil {
		return nil
	}
	if n.left != nil {
		return n.left.minNode()
	} else {
		return n
	}
}

// その部分木内で最大ノード

func (n *AVLNode) maxNode() *AVLNode {
	if n == nil {
		return nil
	}
	if n.right != nil {
		return n.right.maxNode()
	} else {
		return n
	}
}

type AVLTree struct {
	root *AVLNode
	size int
}

func newAVLtree() *AVLTree {
	return new(AVLTree)
}

// keyを挿入
func (t *AVLTree) insert(key int) {
	if t == nil {
		return
	}
	t.root = t.root.insert(key)
	t.size++
}

// keyを削除
func (t *AVLTree) remove(key int) {
	if t == nil {
		return
	}
	t.root = t.root.remove(key)
	t.size--
}

// keyを探索 なければnil
func (t *AVLTree) search(key int) *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.search(key)
}

// keyより大きい最小のノード なければnil keyと一致するノードがあればそれを返す
func (t *AVLTree) lowerBound(key int) *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.lowerBound(key)
}

// keyより小さい最大のノード なければnil keyと一致するノードがあればそれを返す
func (t *AVLTree) upperBound(key int) *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.upperBound(key)
}

// 最大ノード なければnil
func (t *AVLTree) maxNode() *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.maxNode()
}

// 最小ノード なければnil
func (t *AVLTree) minNode() *AVLNode {
	if t == nil {
		return nil
	}
	return t.root.minNode()
}

// そのノードの1つ後（keyが大きい）のノード なければnil
func (t *AVLTree) nextNode(n *AVLNode) *AVLNode {
	if t == nil {
		return nil
	}
	if n == nil {
		return nil
	}
	if n.right != nil {
		return n.right.minNode()
	}
	return t.lowerBound(n.key + 1)
}

// そのノードの1つ前（keyが小さい）のノード なければnil
func (t *AVLTree) prevNode(n *AVLNode) *AVLNode {
	if t == nil {
		return nil
	}
	if n == nil {
		return nil
	}
	if n.left != nil {
		return n.left.maxNode()
	}
	return t.upperBound(n.key - 1)
}

//////////////////////////////////////
// Priority Queue 優先度付きキュー ヒープ
//////////////////////////////////////

type Item struct {
	priority int
	index    int
}

func newItem(priority int, index int) *Item {
	return &Item{
		priority: priority,
		index:    index,
	}
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// 最小ヒープ
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x any) {
	*pq = append(*pq, x.(*Item))
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func newPriorityQueue(init *Item) *PriorityQueue {
	return &PriorityQueue{init}
}

// Graph

type Edge struct {
	to   int
	cost int // 辺の重み
}

type Graph struct {
	size  int
	edges [][]Edge
}

func newGraph(size int, edges [][]Edge) *Graph {
	g := Graph{
		size:  size,
		edges: edges,
	}
	return &g
}

// 「i個」の頂点を追加
func (g *Graph) addNode(i int) {
	g.size += i
	tmp := make([][]Edge, i)
	g.edges = append(g.edges, tmp...)
}

func (g *Graph) addEdge(from, to, cost int) {
	g.edges[from] = append(g.edges[from], Edge{to: to, cost: cost})
	g.edges[to] = append(g.edges[to], Edge{to: from, cost: cost}) // 有向の場合はなし
}

func (g *Graph) dijkstra(start int) []int {
	dist := newInts(g.size, INF)
	dist[start] = 0
	s := newItem(0, start)
	pq := newPriorityQueue(s)
	for pq.Len() != 0 {
		item := heap.Pop(pq).(*Item)
		v := item.index
		if item.priority > dist[v] {
			continue
		}
		for _, e := range g.edges[v] {
			tmp := dist[v] + e.cost
			if dist[e.to] > tmp {
				dist[e.to] = tmp
				heap.Push(pq, newItem(tmp, e.to))
			}
		}
	}
	return dist
}

func (g *Graph) getRadius() int {
	n := g.size
	dist := make([]int, n)
	distFrom := func(start int) {
		for i := 0; i < n; i++ {
			dist[i] = INF
		}
		dist[start] = 0
		q := make([]int, 0)
		q = append(q, start)
		for len(q) > 0 {
			v := q[0]
			if len(q) == 1 {
				q = nil
			} else {
				q = q[1:]
			}
			for _, u := range g.edges[v] {
				if dist[u.to] == INF {
					dist[u.to] = dist[v] + 1
					q = append(q, u.to)
				}
			}
		}
	}
	distFrom(0)
	max_dist, max_dist_index := -1, -1
	for i := 0; i < n; i++ {
		if max_dist < dist[i] {
			max_dist = dist[i]
			max_dist_index = i
		}
	}
	distFrom(max_dist_index)
	res := -1
	for i := 0; i < n; i++ {
		res = max(res, dist[i])
	}
	return res
}
yukicoder

結果

ソースコード
