結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー ID 21712
提出日時 2025-03-03 14:20:28
言語 Go
(1.23.4)
結果
AC  
実行時間 1,816 ms / 2,000 ms
コード長 7,345 bytes
コンパイル時間 12,923 ms
コンパイル使用メモリ 234,720 KB
実行使用メモリ 13,008 KB
スコア 307,498,752
最終ジャッジ日時 2025-03-03 14:22:16
合計ジャッジ時間 107,908 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

const (
	N int = 50
	M int = 1e8
)

func main() {
	var ns string
	Scan(&ns)
	if ns == "LOCAL" {
		runLocal()
		return
	}
	var n int
	Sscan(ns, &n)
	a := make([][]int, n)
	for i := range a {
		a[i] = make([]int, i+1)
		for j := range a[i] {
			Scan(&a[i][j])
		}
	}
	for i, v := range solve(n, a)  {
		if i > 0 {
			Print(" ")
		}
		Print(v)
	}
	Println()
}

func runLocal() {
	var seed int64
	var disp int
	Scan(&seed, &disp)
	a := generate(seed)
	Println("input:")
	if (disp&1) != 0 {
		showPyramid(a)
	} else {
		Println("(omit)")
	}
	ans := solve(N, a)
	Print("ans:")
	if (disp&2) != 0 {
		for _, v := range ans {
			Printf(" %8d", v)
		}
		Println()
	} else {
		Println("(omit)")
	}
	score := calcScore(N, a, ans)
	Printf("max-diff:  %08d\n", score)
	Printf("score:     %08d\n", 5e7-score)
	Printf("score*50: %09d\n", (5e7-score)*50)
	x := make([][]int, N)
	x[N-1] = ans[:]
	for i := N-2; i >= 0; i-- {
		x[i] = make([]int, i+1)
		for j := range x[i] {
			x[i][j] = (x[i+1][j]+x[i+1][j+1])%M
		}
	}
	Println("actual:")
	if (disp&4) != 0 {
		showPyramid(x)
	} else {
		Println("(omit)")
	}
	for i, row := range a {
		for j, v := range row {
			d := abs(x[i][j] - v)
			x[i][j] = min(d, M - d)
		}
	}
	Println("diffs:")
	if (disp&8) != 0 {
		showPyramid(x)
	} else {
		Println("(omit)")
	}
}

func generate(seed int64) [][]int {
	r := rand.New(rand.NewSource(seed))
	a := make([][]int, N)
	for i := range a {
		a[i] = make([]int, i+1)
		for j := range a[i] {
			a[i][j] = r.Intn(M)
		}
	}
	return a
}

func showPyramid(a [][]int) {
	for i, row := range a {
		Printf("[%2d]", i)
		for _, v := range row {
			Printf(" %8d", v)
		}
		Println()
	}
}

var calcScore_tmp []int = nil
func calcScore(n int, a [][]int, c []int) (score int) {
	if calcScore_tmp == nil {
		calcScore_tmp = make([]int, n)
	}
	copy(calcScore_tmp, c)
	for i := n-1; i >= 0; i-- {
		for j, v := range a[i] {
			d := abs(v - calcScore_tmp[j])
			score = max(score, min(d, M-d))
			if j+1<len(calcScore_tmp) {
				calcScore_tmp[j] += calcScore_tmp[j+1]
				calcScore_tmp[j] %= M
			}
		}
	}
	return
}

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

func diff(a, b int) int {
	d := abs(a - b)
	return min(d, M-d)
}

func diffe(a, b [][]int, row, col int) int {
	return diff(a[row][col], b[row][col])
}

func random(a, limit int) int {
	for {
		x := rand.Intn(M)
		if diff(a, x) < limit {
			return x
		}
	}
}

func keepout(a, c, limit int) [][]int {
	l1,r1 := a+(limit+1), a+(M-limit)
	r2,l2 := a-(limit+1), a-(M-limit)
	return [][]int{
		[]int{l1-c,r1-c},
		[]int{l2-c,r2-c},
	}
}

func enterable(kps [][]int) (int, [][]int) {
	for _, kp := range kps {
		if kp[0] >= 0 && kp[1] < M {
			continue
		}
		switch {
			case kp[0] < 0 && kp[1] < 0:
				kp[0] = (kp[0]+10*M)%M
				kp[1] = (kp[1]+10*M)%M
			case kp[0] >= M && kp[1] >= M:
				kp[0] %= M
				kp[1] %= M
			case kp[0] < 0 && kp[1] >= 0:
				kp[0] = (kp[0]+10*M)%M
				kp[1] %= M
			case kp[0] < M && kp[1] >= M:
				kp[1] %= M
		}
		if kp[0] > kp[1] {
			kps = append(kps, []int{0, kp[1]})
			kp[1] = M-1
		}
	}
	sort.Slice(kps, func(i, j int) bool {
		if d := kps[i][0] - kps[j][0]; d != 0 {
			return d < 0
		} else {
			return kps[i][1] < kps[j][1]
		}
	})
	size := 0
	ok := 0
	res := [][]int{}
	for i := 0; i < len(kps) && ok < M; i++ {
		if i+1<len(kps) && kps[i][1] >= kps[i+1][0] {
			kps[i+1][0] = kps[i][0]
			if kps[i][1] > kps[i+1][1] {
				kps[i+1][1] = kps[i][1]
			}
		} else {
			if ok < kps[i][0] {
				res = append(res, []int{ ok, kps[i][0]-1 })
				size += kps[i][0] - ok
			}
			ok = max(ok, kps[i][1]+1)
		}
	}
	if ok < M {
		res = append(res, []int{ ok, M-1 })
		size += M-ok
	}
	return size, res
}

type FState struct {
	score, next int
	ans, ladder [N]int
}

type FStateList []*FState

func (sl FStateList) Len() int { return len(sl) }
func (sl FStateList) Swap(i, j int) {
	sl[i], sl[j] = sl[j], sl[i]
}
func (sl FStateList) Less(i, j int) bool {
	return sl[i].score < sl[j].score
}

func samples(sampleSize, entSizeSum int, ent [][]int) (res []int) {
	if entSizeSum <= sampleSize {
		res = make([]int, 0, entSizeSum)
		for _, lu := range ent {
			for i := lu[0]; i <= lu[1]; i++ {
				res = append(res, i)
			}
		}
	} else {
		tmp := make([]int, sampleSize*2)
		res = tmp[:0]
		for _, lu := range ent {
			size := lu[1]-lu[0]+1
			if size == 1 {
				tmp[0] = lu[0]
				res = res[:len(res)+1]
				tmp = tmp[1:]
				continue
			}
			c := int((int64(size)*int64(sampleSize)+int64(entSizeSum-1))/int64(entSizeSum))
			if c == 1 {
				tmp[0] = rand.Intn(size)+lu[0]
				res = res[:len(res)+1]
				tmp = tmp[1:]
				continue
			}
			sum := 0
			for i := 0; i < c; i++ {
				sum += i + rand.Intn(10)
				tmp[i] = sum
			}
			sum += rand.Intn(10)
			for i := 0; i < c; i++ {
				tmp[i] = (size-1)*tmp[i]/sum+lu[0]
			}
			res = res[:len(res)+c]
			tmp = tmp[c:]
		}
	}
	return
}

func solve(n int, a [][]int) (ans []int) {
	
	ch := time.After(1800 * time.Millisecond)
	
	// うっかりツイッターで解法を目にしてしまった
	// おわりです
	
	ra := make([][]int, n)
	for i, row := range a {
		ra[n-1-i] = row[:]
	}
	x := make([][]int, n)
	for i := range x {
		x[n-1-i] = make([]int, i+1)
	}
	ans = make([]int, n)
	
	score := M

	target := M/2-M/100*5
	
	const C = 40
	
	states := make(FStateList, 0, C*C)
	tmpStates := make(FStateList, 0, C*C)
	
	var ladder [N]int

	for {
		if len(states) == 0 {
			for i := 0; i < C*C; i++{
				e := random(ra[0][0],target+1)%M
				st := new(FState)
				st.score = diff(ra[0][0], e)
				st.next = 1
				st.ans[0] = e 
				st.ladder[0] = e
				states = append(states, st)
			}
		}
		sort.Sort(states)
		states = states[:min(C,len(states))]
		tmpStates = tmpStates[:0]
		for _, st := range states[:min(C,len(states))] {
			select {
				case <-ch:
					return
				default:
			}
			i := st.next
			kps := [][]int{}
			ladder[0] = 0
			kps = append(kps, keepout(ra[0][i], ladder[0], target)...)
			for py,px:=0,i; px>0; py,px=py+1,px-1 {
				ladder[py+1] = (st.ladder[py]+ladder[py])%M
				kps = append(kps, keepout(ra[py+1][px-1], ladder[py+1], target)...)
			}
			size, ent := enterable(kps)
			if len(ent) == 0 || size == 0 {
				continue
			}
			smp := samples(C, size, ent)
			if i + 1 == n {
				for _, v := range smp {
					ladder[0] = v
					tmp := max(st.score, diff(ra[0][i], ladder[0])) 
					for py,px:=0,i; px>0; py,px=py+1,px-1 {
						ladder[py+1] = (st.ladder[py]+ladder[py])%M
						tmp = max(tmp, diff(ra[py+1][px-1], ladder[py+1]))
					}
					if tmp < score {
						score = tmp
						copy(ans, st.ans[:])
						ans[i] = v
						target = min(target, score - M/500)
					}
				}
			} else {
				for _, v := range smp {
					nst := new(FState)
					nst.next = i + 1
					copy(nst.ans[:], st.ans[:])
					nst.ans[i] = v
					nst.ladder[0] = v
					nst.score = max(st.score, diff(ra[0][i], nst.ladder[0])) 
					for py,px:=0,i; px>0; py,px=py+1,px-1 {
						nst.ladder[py+1] = (st.ladder[py]+nst.ladder[py])%M
						nst.score = max(nst.score, diff(ra[py+1][px-1], nst.ladder[py+1]))
					}
					if nst.score < score {
						tmpStates = append(tmpStates, nst)
					}
				}
			}
		}
		tmpStates, states = states, tmpStates
	}
	return
}
0