結果

問題 No.5007 Steiner Space Travel
ユーザー ID 21712ID 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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])
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0