結果

問題 No.2596 Christmas Eve (Heuristic ver.)
コンテスト
ユーザー ID 21712
提出日時 2025-03-10 15:13:59
言語 Go
(1.23.4)
結果
AC  
実行時間 52 ms / 1,224 ms
コード長 6,935 bytes
コンパイル時間 13,322 ms
コンパイル使用メモリ 255,144 KB
実行使用メモリ 18,900 KB
スコア 3,640,627
最終ジャッジ日時 2025-03-10 15:14:31
合計ジャッジ時間 30,653 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 125
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

type Unit struct {
	Id, Width, Height int
}

func solve(n, k int, a, b, c, d, e, f []int) (res [][]int) {
	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
				}
			}
		}
	}
	
	founds := make([]int, 0, n)
	for tri, tpi := range connTrtps {
		if tpi < 0 {
			continue
		}
		founds = append(founds, tri)
	}
	
	slices.SortFunc(founds, func(tri1, tri2 int) int {
		tpi1 := connTrtps[tri1]
		lvs1 := connTplvs[tpi1]
		h1 := tops[tpi1].Height+
			leaves[lvs1[0]].Height+
			leaves[lvs1[1]].Height+
			trunks[tri1].Height
		tpi2 := connTrtps[tri2]
		lvs2 := connTplvs[tpi2]
		h2 := tops[tpi2].Height+
			leaves[lvs2[0]].Height+
			leaves[lvs2[1]].Height+
			trunks[tri2].Height
		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 := tops[tpi1].Height+
			leaves[lvs1[0]].Height+
			leaves[lvs1[1]].Height+
			trunks[tri1].Height
		tpi2 := connTrtps[tri2]
		lvs2 := connTplvs[tpi2]
		h2 := tops[tpi2].Height+
			leaves[lvs2[0]].Height+
			leaves[lvs2[1]].Height+
			trunks[tri2].Height
		d := h2 - h1
		if d < bestd {
			besti, bestd = i, d
		}
	}
	
	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
		}
	}
	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("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
}
0