結果

問題 No.2596 Christmas Eve (Heuristic ver.)
ユーザー ID 21712
提出日時 2025-03-11 12:18:07
言語 Go
(1.23.4)
結果
AC  
実行時間 1,206 ms / 1,224 ms
コード長 11,271 bytes
コンパイル時間 12,419 ms
コンパイル使用メモリ 240,220 KB
実行使用メモリ 19,068 KB
スコア 4,960,723
最終ジャッジ日時 2025-03-11 12:21:03
合計ジャッジ時間 175,076 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 125
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"cmp"
	. "fmt"
	"math"
	"math/rand"
	"slices"
	"sort"
	"time"
)

type Unit struct {
	Id, Width, Height int
}

func solve(n, k int, a, b, c, d, e, f []int) (res [][]int) {
	ch := time.After(1180 * time.Millisecond)
	
	tops := make([]*Unit, n)
	for i := range tops {
		tops[i] = &Unit{
			Id: i+1,
			Width: a[i],
			Height: b[i],
		}
	}
	leaves := make([]*Unit, n*2)
	for i := range leaves {
		leaves[i] = &Unit{
			Id: i+1,
			Width: c[i],
			Height: d[i],
		}
	}
	trunks := make([]*Unit, n)
	for i := range trunks {
		trunks[i] = &Unit{
			Id: i+1,
			Width: e[i],
			Height: f[i],
		}
	}
	slices.SortFunc(tops, func(a, b *Unit) int {
		return cmp.Compare(a.Width, b.Width)
	})
	slices.SortFunc(leaves, func(a, b *Unit) int {
		return cmp.Compare(a.Width, b.Width)
	})
	slices.SortFunc(trunks, func(a, b *Unit) int {
		return cmp.Compare(a.Width, b.Width)
	})
	trtps := make([][]int, n)
	tptrs := make([][]int, n)
	for i, tru := range trunks {
		for j, tpu := range tops {
			if tru.Width < tpu.Width {
				trtps[i] = append(trtps[i], j)
				tptrs[j] = append(tptrs[j], i)
			}
		}
	}
	tplvs := make([][]int, n)
	lvtps := make([][]int, n*2)
	for i, tpu := range tops {
		for j, lvu := range leaves {
			if tpu.Width < lvu.Width {
				tplvs[i] = append(tplvs[i], j)
				lvtps[j] = append(lvtps[j], i)
			}
		}
	}
	connTrtps := make([]int, n)
	connTptrs := make([]int, n)
	connTplvs := make([][]int, n)
	connLvtps := make([]int, n*2)
	for i := range connTrtps {
		connTrtps[i] = -1
		connTptrs[i] = -1
		connTplvs[i] = []int{ -1, -1}
		connLvtps[i] = -1
		connLvtps[i+n] = -1
	}
	
outer1:
	for tri, tps := range trtps {
		if connTrtps[tri] >= 0 {
			continue
		}
		for _, tpi := range tps {
			if connTptrs[tpi] >= 0 {
				continue
			}
			for i, lv1i := range tplvs[tpi] {
				if connLvtps[lv1i] >= 0 {
					continue
				}
				for _, lv2i := range tplvs[tpi][i+1:] {
					if connLvtps[lv2i] >= 0 {
						continue
					}
					connTrtps[tri] = tpi
					connTptrs[tpi] = tri
					connTplvs[tpi][0] = lv1i
					connTplvs[tpi][1] = lv2i
					connLvtps[lv1i] = tpi
					connLvtps[lv2i] = tpi
					continue outer1
				}
			}
		}
	}
	
	height := func(tpi, lv1i, lv2i, tri int) int {
		return tops[tpi].Height+
			leaves[lv1i].Height+
			leaves[lv2i].Height+
			trunks[tri].Height
	}
	
	bestScore := int(1e9)
	
	makeSolution := func() bool {
		founds := make([]int, 0, n)
		for tri, tpi := range connTrtps {
			if tpi < 0 {
				continue
			}
			founds = append(founds, tri)
		}
		
		if len(founds) < k {
			return false
		}
		
		slices.SortFunc(founds, func(tri1, tri2 int) int {
			tpi1 := connTrtps[tri1]
			lvs1 := connTplvs[tpi1]
			h1 := height(tpi1, lvs1[0], lvs1[1], tri1)
			tpi2 := connTrtps[tri2]
			lvs2 := connTplvs[tpi2]
			h2 := height(tpi2, lvs2[0], lvs2[1], tri2)
			return cmp.Compare(h1, h2)
		})
		
		besti, bestd := 0, int(1e9)
		for i := 0; i+k <= len(founds); i++ {
			tri1 := founds[i]
			tri2 := founds[i+k-1]
			tpi1 := connTrtps[tri1]
			lvs1 := connTplvs[tpi1]
			h1 := height(tpi1, lvs1[0], lvs1[1], tri1)
			tpi2 := connTrtps[tri2]
			lvs2 := connTplvs[tpi2]
			h2 := height(tpi2, lvs2[0], lvs2[1], tri2)
			d := h2 - h1
			if d < bestd {
				besti, bestd = i, d
			}
		}
		
		if bestd >= bestScore {
			return false
		}
		
		// println(Sprintf("update: %d", bestd))
		
		bestScore = bestd
		
		res = make([][]int, 0, k)
		for _, tri := range founds[besti:] {
			tpi := connTrtps[tri]
			lvs := connTplvs[tpi]
			res = append(res, []int{
				tops[tpi].Id,
				leaves[lvs[0]].Id,
				leaves[lvs[1]].Id,
				trunks[tri].Id,
			})
			if len(res) == k {
				return true
			}
		}
		return false
	}

	// make provisional solution
	makeSolution()
	
	makeResult := func() {
		i := 0
		for tpi, tri := range connTptrs {
			if tri < 0 {
				continue
			}
			lvs := connTplvs[tpi]
			tmp := res[i][:]
			tmp[0] = tops[tpi].Id
			tmp[1] = leaves[lvs[0]].Id
			tmp[2] = leaves[lvs[1]].Id
			tmp[3] = trunks[tri].Id
			i++
		}
	}
	
	combine := func(tpi, lv1i, lv2i, tri int) {
		// no validatation
		connTptrs[tpi] = tri
		connTplvs[tpi][0] = lv1i
		connTplvs[tpi][1] = lv2i
		connTrtps[tri] = tpi
		connLvtps[lv1i] = tpi
		connLvtps[lv2i] = tpi
	}
	
	destroy := func(tpi int) {
		tri := connTptrs[tpi]
		lvs := connTplvs[tpi]
		connTrtps[tri] = -1
		connLvtps[lvs[0]] = -1
		connLvtps[lvs[1]] = -1
		connTptrs[tpi] = -1
		lvs[0] = -1
		lvs[1] = -1
	}
	
	{
		founds := make([]int, 0, n)
		for tpi, tri := range connTptrs {
			if tri < 0 {
				continue
			}
			founds = append(founds, tpi)
		}
		slices.SortFunc(founds, func(tpi1, tpi2 int) int {
			tri1 := connTptrs[tpi1]
			lvs1 := connTplvs[tpi1]
			h1 := height(tpi1, lvs1[0], lvs1[1], tri1)
			tri2 := connTptrs[tpi2]
			lvs2 := connTplvs[tpi2]
			h2 := height(tpi2, lvs2[0], lvs2[1], tri2)
			return cmp.Compare(h1, h2)
		})
		besti, bestd := -1, int(1e9)
		for i := 0; i+k <= len(founds); i++ {
			tpi1 := founds[i]
			tpi2 := founds[i+k-1]
			tri1 := connTptrs[tpi1]
			lvs1 := connTplvs[tpi1]
			h1 := height(tpi1, lvs1[0], lvs1[1], tri1)
			tri2 := connTptrs[tpi2]
			lvs2 := connTplvs[tpi2]
			h2 := height(tpi2, lvs2[0], lvs2[1], tri2)
			d := h2-h1
			if d < bestd {
				besti, bestd = i, d
			}
		}
		for i, tpi := range founds {
			if besti <= i && i < besti+k {
				continue
			}
			destroy(tpi)
		}
	}
	
	perms := make([][]int, n+1)
	for i := range perms {
		if i == 0 {
			perms[0] = []int{}
		} else {
			perms[i] = rand.Perm(i)
		}
	}
	get := func(i int) []int {
		perm := perms[i]
		rand.Shuffle(i, func(i, j int) {
			sort.IntSlice(perm).Swap(i, j)
		})
		return perm
	}
	
	tphs := make([]int, n)
	for tpi := range tphs {
		tri := connTptrs[tpi]
		if tri < 0 {
			continue
		}
		lvs := connTplvs[tpi]
		tphs[tpi] = height(tpi, lvs[0], lvs[1], tri)
	}

	trs := make([]int, n)
	lvs := make([]int, n*2)
	for {
		select {
			case <-ch:
				return
			default:
		}
		mintpi, maxtpi := -1, -1
		minh, maxh := int(1e9), 0
		for tpi, tri := range connTptrs {
			if tri < 0 {
				continue
			}
			h := tphs[tpi]
			if h < minh {
				mintpi, minh = tpi, h
			}
			if h > maxh {
				maxtpi, maxh = tpi, h
			}
		}
		if maxh - minh < bestScore {
			bestScore = maxh - minh
			makeResult()
		}
		half := (maxh + minh) / 2
		if half - minh < maxh - half {
			destroy(maxtpi)
		} else {
			destroy(mintpi)
		}
		for {
			select {
				case <-ch:
					return
				default:
			}
			besttpi, besttri, bestlv1i, bestlv2i := -1,-1,-1,-1
			bestd, besth := int(1e9), 0
			for tpi, tri0 := range connTptrs {
				if tri0 >= 0 {
					continue
				}
				trs = trs[:0]
				for _, tri := range tptrs[tpi] {
					if connTrtps[tri] < 0 {
						trs = append(trs, tri)
					}
				}
				if len(trs) == 0 {
					continue
				}
				trc := min(len(trs), 4)
				trps := get(len(trs))[:trc]
				lvs := lvs[:0]
				for _, lvi := range tplvs[tpi] {
					if connLvtps[lvi] < 0 {
						lvs = append(lvs, lvi)
					}
				}
				if len(lvs) == 0 {
					continue
				}
				lvc := min(len(lvs), 4)
				lvps := get(len(lvs))[:lvc]
				for _, x := range trps {
					tri := trs[x]
					for i, y := range lvps {
						lv1i := lvs[y]
						for _, z := range lvps[i+1:] {
							lv2i := lvs[z]
							h := height(tpi, lv1i, lv2i, tri)
							if h <= minh || maxh <= h {
								continue
							}
							d := half - h
							if d < 0 {
								d = -d
							}
							if d < bestd {
								besttpi = tpi
								besttri = tri
								bestlv1i = lv1i
								bestlv2i = lv2i
								bestd = d
								besth = h
							}
						}
					}
				}
			}
			if besttpi >= 0 {
				combine(besttpi, bestlv1i, bestlv2i, besttri)
				tphs[besttpi] = besth
				break
			}
		}
	}

	return
}

func main() {
	var ns string
	Scan(&ns)
	if ns == "LOCAL" {
		runLocal()
		return
	}
	var n, k int
	Sscan(ns, &n)
	Scan(&k)
	a := make([]int, n)
	b := make([]int, n)
	c := make([]int, n*2)
	d := make([]int, n*2)
	e := make([]int, n)
	f := make([]int, n)
	for _, vs := range [][]int{a,b,c,d,e,f} {
		for i := range vs {
			Scan(&vs[i])
		}
	}
	ans := solve(n, k, a, b, c, d, e, f)
	for _, vs := range ans {
		Println(vs[0], vs[1], vs[2], vs[3])
	}
}

func runLocal() {
	Println("RUN LOCAL")
	const N = 500
	var seed int64 = rand.Int63()
	Scan(&seed)
	k, a, b, c, d, e, f := generate(seed, N)
	ans := solve(N, k, a, b, c, d, e, f)
	validate(N, k, a, c, e, ans)
	hmin, hmax := int(1e9), 0
	for _, vs := range ans {
		h := b[vs[0]-1]+d[vs[1]-1]+d[vs[2]-1]+f[vs[3]-1]
		if h < hmin {
			hmin = h
		}
		if h > hmax {
			hmax = h
		}
	}
	Println("hmin =", hmin)
	Println("hmax =", hmax)
	Println("diff =", hmax-hmin)
	Println("score =", 4e4-(hmax-hmin))
	Println("score*125 =", 125*(4e4-(hmax-hmin)))
}

func validate(n, k int, a, c, e []int, res [][]int) {
	if len(res) != k {
		panic("len != k")
	}
	usedTops := make([]bool, n+1)
	usedLeaves := make([]bool, n*2+1)
	usedTrunks := make([]bool, n+1)
	for i, vs := range res {
		if len(vs) != 4 {
			panic(Sprintf("[%d] %#v (len != 4)", i, vs))
		}

		if vs[0] < 1 || n < vs[0] {
			panic(Sprintf("[%d] %#v (invalid id [0])", i, vs))
		}
		if usedTops[vs[0]] {
			panic(Sprintf("[%d] %#v (duplicate id [0])", i, vs))
		}
		usedTops[vs[0]] = true

		if vs[1] < 1 || 2*n < vs[1] {
			panic(Sprintf("[%d] %#v (invalid id [1])", i, vs))
		}
		if usedLeaves[vs[1]] {
			panic(Sprintf("[%d] %#v (duplicate id [1])", i, vs))
		}
		usedLeaves[vs[1]] = true

		if vs[2] < 1 || 2*n < vs[2] {
			panic(Sprintf("[%d] %#v (invalid id [2])", i, vs))
		}
		if usedLeaves[vs[2]] {
			panic(Sprintf("[%d] %#v (duplicate id [2])", i, vs))
		}
		usedLeaves[vs[2]] = true

		if vs[3] < 1 || n < vs[3] {
			panic(Sprintf("[%d] %#v (invalid id [3])", i, vs))
		}
		if usedTrunks[vs[3]] {
			panic(Sprintf("[%d] %#v (duplicate id [3])", i, vs))
		}
		usedTrunks[vs[3]] = true

		if a[vs[0]-1] <= e[vs[3]-1] {
			panic(Sprintf("[%d] %#v (a <= e)", i, vs))
		}
		if c[vs[1]-1] <= a[vs[0]-1] {
			panic(Sprintf("[%d] %#v (c1 <= a)", i, vs))
		}
		if c[vs[2]-1] <= a[vs[0]-1] {
			panic(Sprintf("[%d] %#v (c2 <= a)", i, vs))
		}
	}
}

func generate(seed int64, n int) (k int, a,b,c,d,e,f []int) {
	rng := rand.New(rand.NewSource(seed))
	smp := func(min, max, stddev, mean int) int {
		v := rng.NormFloat64()*float64(stddev)+float64(mean)
		return int(math.Max(float64(min),math.Min(float64(max),v)))
	}
	k = rng.Intn(101) + 300
	a = make([]int, n)
	b = make([]int, n)
	c = make([]int, n*2)
	d = make([]int, n*2)
	e = make([]int, n)
	f = make([]int, n)
	for i := 0; i < k; i++ {
		var w [4]int
		for {
			for j := range w[:] {
				w[j] = smp(1, 1e4, 1600, 5000)
			}
			slices.Sort(w[:])
			if len(slices.Compact(w[:])) == 4 {
				break
			}
		}
		a[i] = w[1]
		c[i] = w[2]
		c[i+n] = w[3]
		e[i] = w[0]
	}
	for i := k; i < n; i++ {
		a[i] = smp(1, 1e4, 1600, 5000)
		c[i] = smp(1, 1e4, 1600, 5000)
		c[i+n] = smp(1, 1e4, 1600, 5000)
		e[i] = smp(1, 1e4, 1600, 5000)
	}
	rng.Shuffle(len(a), func(i, j int) {
		sort.IntSlice(a).Swap(i, j)
	})
	rng.Shuffle(len(c), func(i, j int) {
		sort.IntSlice(c).Swap(i, j)
	})
	rng.Shuffle(len(e), func(i, j int) {
		sort.IntSlice(e).Swap(i, j)
	})
	for i, v := range a {
		b[i] = smp(1, 1e4, 500, v)
	}
	for i, v := range c {
		d[i] = smp(1, 1e4, 500, v)
	}
	for i, v := range e {
		f[i] = smp(1, 1e4, 500, v)
	}
	return
}

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