結果

問題 No.5021 Addition Pyramid
ユーザー ID 21712
提出日時 2025-03-03 03:55:47
言語 Go
(1.23.4)
結果
AC  
実行時間 1,716 ms / 2,000 ms
コード長 8,089 bytes
コンパイル時間 11,128 ms
コンパイル使用メモリ 238,284 KB
実行使用メモリ 8,748 KB
スコア 326,908,326
最終ジャッジ日時 2025-03-03 03:57:21
合計ジャッジ時間 89,659 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

const (
	N int = 50
	M int = 1e8

	Target = M/2-M/100*7
)

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
	Scanf("%d%b", &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]+2*M)%M
				kp[1] = (kp[1]+2*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]+2*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
}

func solve(n int, a [][]int) (ans []int) {
	var score int
	score, ans = solveLow(M/2-M/100*5, n, a)
	{
		ts, ta := solveLow(M/2-M/100*6, n, a)
		if ts < score {
			score, ans = ts, ta
		}
	}
	for q := 0; q < 3; q++ {
		ts, ta := solveLow(M/2-M/100*64/10, n, a)
		if ts < score {
			score, ans = ts, ta
			if score <= Target {
				break
			}
		}
	}
	for q := 0; q < 4; q++ {
		ts, ta := solveLow(M/2-M/100*66/10, n, a)
		if ts < score {
			score, ans = ts, ta
			if score <= Target {
				break
			}
		}
	}
	for q := 0; q < 9; q++ {
		ts, ta := solvep(n, a)
		if ts < score {
			score, ans = ts, ta
			if score <= Target {
				break
			}
		}
	}
	return
}

func solvep(n int, a [][]int) (score int, ans []int) {
	
	// うっかりツイッターで解法を目にしてしまった
	// おわりです
	
	ch := time.After( 100 * 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
	
	
	ents := make([][][]int, n)
	sizes := make([]int, n)
	cnts := make([]int, n)

outer:
	for q := 0; q < 1e3; q++ {
		clear(ents)
		clear(sizes)
		clear(cnts)
		// x[0][0] = (ra[0][0]+Target)%M
		x[0][0] = random(ra[0][0], Target)
		for i := 1; i < n; i++ {
			select {
				case <-ch:
					return
				default:
			}
			cnts[i]++
			if len(ents[i]) == 0 {
				kps := [][]int{}
				x[0][i] = 0
				kps = append(kps, keepout(ra[0][i], x[0][i], Target)...)
				for py,px:=0,i; px>0; py,px=py+1,px-1 {
					x[py+1][px-1] = (x[py][px-1]+x[py][px])%M
					kps = append(kps, keepout(ra[py+1][px-1], x[py+1][px-1], Target)...)
				}
				sizes[i], ents[i] = enterable(kps)
				// println(Sprintf("[%02d](%2d) %#v", i, len(ent), ent))
				if len(ents[i]) == 0 || sizes[i] == 0 {
					if cnts[i] > 100 || cnts[i]*4 > sizes[i-1] || rand.Intn(1000) < 21  {
						if i-2 < 1 || rand.Intn(1000) < 11 {
							continue outer
						}
						cnts[i] = 0
						cnts[i-1] = 0
						ents[i-1] = nil
						sizes[i-1] = 0
						i -= 3
						continue
					} else {
						i -= 2
						continue
					}
				}
			}
			z := ents[i][rand.Intn(len(ents[i]))][:]
			e := rand.Intn(z[1]-z[0])+z[0]
			x[0][i] = e % M
			for py,px:=0,i; px>0; py,px=py+1,px-1 {
				x[py+1][px-1] = (x[py][px-1]+x[py][px])%M
			}
		}
		tmp := calcScore(n, a, x[0][:])
		if tmp < score {
			score = tmp
			copy(ans, x[0][:])
			if score <= Target {
				break outer
			}
		}
	}
	return
}


func solveLow(LowTarget, n int, a [][]int) (score int, ans []int) {
	
	ch := time.After( 100 * 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
	
	
	ents := make([][][]int, n)
	sizes := make([]int, n)
	cnts := make([]int, n)

outer:
	for q := 0; q < 1e3; q++ {
		clear(ents)
		clear(sizes)
		clear(cnts)
		// x[0][0] = (ra[0][0]+LowTarget)%M
		x[0][0] = random(ra[0][0], LowTarget)
		for i := 1; i < n; i++ {
			select {
				case <-ch:
					return
				default:
			}
			cnts[i]++
			if len(ents[i]) == 0 {
				kps := [][]int{}
				x[0][i] = 0
				kps = append(kps, keepout(ra[0][i], x[0][i], LowTarget)...)
				for py,px:=0,i; px>0; py,px=py+1,px-1 {
					x[py+1][px-1] = (x[py][px-1]+x[py][px])%M
					kps = append(kps, keepout(ra[py+1][px-1], x[py+1][px-1], LowTarget)...)
				}
				sizes[i], ents[i] = enterable(kps)
				// println(Sprintf("[%02d](%2d) %#v", i, len(ent), ent))
				if len(ents[i]) == 0 || sizes[i] == 0 {
					if cnts[i] > 100 || cnts[i]*4 > sizes[i-1] || rand.Intn(1000) < 21  {
						if i-2 < 1 || rand.Intn(1000) < 11 {
							continue outer
						}
						cnts[i] = 0
						cnts[i-1] = 0
						ents[i-1] = nil
						sizes[i-1] = 0
						i -= 3
						continue
					} else {
						i -= 2
						continue
					}
				}
			}
			z := ents[i][rand.Intn(len(ents[i]))][:]
			e := rand.Intn(z[1]-z[0])+z[0]
			x[0][i] = e % M
			for py,px:=0,i; px>0; py,px=py+1,px-1 {
				x[py+1][px-1] = (x[py][px-1]+x[py][px])%M
			}
		}
		tmp := calcScore(n, a, x[0][:])
		if tmp < score {
			score = tmp
			copy(ans, x[0][:])
			if score <= LowTarget {
				break outer
			}
		}
	}
	return
}
0