#1039910 (Go) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: ID 21712
• 提出日時: 2025-01-30 13:27:52
• 言語: Go (1.23.4)
• 結果: AC
• 実行時間: 824 ms / 1,000 ms
• コード長: 5,110 bytes
• コンパイル時間: 14,119 ms
• コンパイル使用メモリ: 248,928 KB
• 実行使用メモリ: 50,068 KB
• スコア: 8,051,001
• 最終ジャッジ日時: 2025-01-30 13:28:32
• 合計ジャッジ時間: 39,821 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
other	AC * 30

ソースコード

package main

import . "fmt"
import "math/rand"
import "sort"
import . "math"

const ALPHA = 5

func dist(a,b []int, i int, c,d []int, j int) int {
	dx := a[i] - c[j]
	dy := b[i] - d[j]
	return dx*dx + dy*dy
}

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

func max(a, b int) int {
	return a+b-min(a,b)
}

func main() {
	var n, m int
	Scan(&n, &m)
	a := make([]int, n)
	b := make([]int, n)
	for i := range a {
		Scan(&a[i],&b[i])
	}
	
	c := make([]int, m+1)
	d := make([]int, m+1)

	h := make([][]int, 1001)
	hh := make([][]int, 1001)
	for i := range h {
		h[i] = make([]int, 1001)
		hh[i] = make([]int, 1001)
	}

	const DR1 = 150
	const DR2 = 100
	const DR3 = 250
	for i, x := range a {
		y := b[i]
		for dy := max(0,y-DR1)-y; dy <= DR1 && y+dy <= 1000; dy++ {
			dx := int(Floor(Sqrt(DR1*DR1-float64(dy*dy))))
			hh[y+dy][max(0,x-dx)]++
			if x+dx+1 <= 1000 {
				hh[y+dy][x+dx+1]--
			}
			if dy < -DR2 || DR2 < dy {
				continue
			}
			dx = int(Floor(Sqrt(DR2*DR2-float64(dy*dy))))
			hh[y+dy][max(0,x-dx)]--
			if x+dx+1 <= 1000 {
				hh[y+dy][x+dx+1]++
			}
		}
	}
	for i, row := range hh {
		xx := 0
		for j, vhh := range row {
			xx += vhh
			h[i][j] = xx
			hh[i][j] = 0
		}
	}
	id := 0
	area := [][]int{}
	for i, row := range h {
		for j, vh := range row {
			if vh == 0 || hh[i][j] != 0 {
				continue
			}
			id++
			var cnt, yy, xx int
			dfs := []int{i, j}
			for len(dfs) > 0 {
				y,x:=dfs[len(dfs)-2],dfs[len(dfs)-1]
				dfs = dfs[:len(dfs)-2]
				if h[y][x] != vh || hh[y][x] != 0 {
					continue
				}
				cnt++
				yy += y
				xx += x
				hh[y][x] = id
				if x > 0 {
					dfs = append(dfs, y,x-1)
				}
				if x < 1000 {
					dfs = append(dfs, y,x+1)
				}
				if y > 0 {
					dfs = append(dfs, y-1,x)
				}
				if y < 1000 {
					dfs = append(dfs, y+1,x)
				}
			}
			yy = min(1000, max(0, yy/cnt))
			xx = min(1000, max(0, xx/cnt))
			area = append(area, []int{vh, cnt, yy, xx})
		}
	}
	sort.Slice(area, func(i, j int) bool {
		return area[i][0]>area[j][0]
	})
	// println(Sprintf("%#v", area))

	for i := range c {
		c[i] = (i%3+1)*250
		d[i] = (i/3+1)*250
	}
	c[m/2] = c[m]
	d[m/2] = d[m]
	c = c[:m]
	d = d[:m]
	
	cc := 0
	for _, e := range area[len(area)/2:] {
		ok := true
		for i := 0; i < cc; i++ {
			dx := c[i]-e[3]
			dy := d[i]-e[2]
			ok = ok && (dx*dx+dy*dy>DR3*DR3)
		}
		if ok {
			c[cc] = e[3]
			d[cc] = e[2]
			cc++
			if cc == m {
				break
			}
		}
	}
	
	path := make([][][]int, n+m)
	for i := range path {
		path[i] = make([][]int, n+m)
		for j := range path[i] {
			switch {
				case i == j:
					path[i][j] = []int{ 0, j }
				case i < n && j < n:
					path[i][j] = []int{
						ALPHA*ALPHA*dist(a,b,i,a,b,j),
						j,
					}
				case i < n:
					path[i][j] = []int{
						ALPHA*dist(a,b,i,c,d,j-n),
						j,
					}
				case j < n:
					path[i][j] = []int{
						ALPHA*dist(c,d,i-n,a,b,j),
						j,
					}
				default:
					path[i][j] = []int{
						dist(c,d,i-n,c,d,j-n),
						j,
					}
			}
		}
	}
	
	for i := 0; i < n+m; i++ {
		for j := 0; j < n+m; j++ {
			if i == j {
				continue
			}
			for k := 0; k < n+m; k++ {
				if i==k || j==k {
					continue
				}
				if x := path[i][k][0]+path[k][j][0]; x < path[i][j][0] {
					path[i][j][0] = x
					path[i][j][1] = k
				}
			}
		}
	}
	
	p := []int{0}
	for i := 0; i < n; i++ {
		p = append(p, (i+1)%n)
	}
	
	calc := func(p []int) int {
		sc := 0
		for i := 0; i < n; i++ {
			sc += path[p[i]][p[i+1]][0]
		}
		return sc
	}
	
	bestSc := calc(p)
	bestP := make([]int, len(p))
	copy(bestP, p)

	for kk := 0; kk < 70; kk++ {
	
		for cc, changed := 0, true; changed && cc < 100; cc++ {
			changed = false
			// 2-opt ?
			for i := 1; i < n; i++ {
				for j := i+1; j < n; j++ {
					s0 := path[p[i-1]][p[i]][0] +
						path[p[j]][p[j+1]][0]
					s1 := path[p[i-1]][p[j]][0] +
						path[p[i]][p[j+1]][0]
					if s1 < s0 {
						for f,e := i,j; f < e; f,e=f+1,e-1 {
							p[f],p[e] = p[e],p[f]
						}
						changed = true
					}
				}
			}
			// 3-opt ?
			for i := 1; i < n; i++ {
				for j := i+1; j < n; j++ {
					for k := j+2; k < n; k++ {
						s0 := path[p[i-1]][p[i]][0] +
							path[p[j]][p[j+1]][0] +
							path[p[k]][p[k+1]][0]
						s1 := path[p[i-1]][p[j]][0] +
							path[p[i]][p[k]][0] +
							path[p[j+1]][p[k+1]][0]
						if s1 < s0 {
							for f,e := i,j; f < e; f,e=f+1,e-1 {
								p[f],p[e] = p[e],p[f]
							}
							for f,e := j+1,k; f < e; f,e=f+1,e-1 {
								p[f],p[e] = p[e],p[f]
							}
							changed = true
						}
					}
				}
			}
		}
		
		if sc := calc(p); sc < bestSc {
			bestSc = sc
			copy(bestP, p)
		}

		rand.Shuffle(n-1, func(i, j int) {
			p[i+1],p[j+1] = p[j+1],p[i+1]
		})
	}
	
	p = bestP
		
	t := []int{1}
	r := []int{1}
	var add func(i, j int)
	add = func(i, j int) {
		rt := path[i][j]
		if rt[1] == j {
			if j < n {
				t = append(t, 1)
				r = append(r, j+1)
			} else {
				t = append(t, 2)
				r = append(r, j-n+1)
			}
			return
		}
		add(i, rt[1])
		add(rt[1], j)
	}
	
	for i := 0; i < n; i++ {
		add(p[i], p[i+1])
	}
	
	for i := range c {
		Println(c[i], d[i])
	}
	Println(len(t))
	for i := range t {
		Println(t[i], r[i])
	}
	
}