結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー ID 21712
提出日時 2025-03-05 18:10:07
言語 Go
(1.23.4)
結果
AC  
実行時間 1,814 ms / 2,000 ms
コード長 6,255 bytes
コンパイル時間 12,996 ms
コンパイル使用メモリ 249,084 KB
実行使用メモリ 8,756 KB
スコア 319,587,562
最終ジャッジ日時 2025-03-05 18:12:00
合計ジャッジ時間 108,276 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
}

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 {
		res = make([]int, sampleSize)
		sum := 0
		for i := range res {
			sum += (i+i)/(i+1) + rand.Intn(10)
			res[i] = sum
		}
		sum += rand.Intn(10)
		for i, v := range res {
			res[i] = int(int64(entSizeSum)*int64(v)/int64(sum))
		}
		tmp := res[:]
		ssum := 0
		for _, lu := range ent {
			size := lu[1]-lu[0]+1
			for  len(tmp) > 0 && ssum <= tmp[0] && tmp[0] < ssum+size {
				tmp[0] = tmp[0] - ssum + lu[0]
				tmp = tmp[1:]
			}
			ssum += size
			if len(tmp) == 0 {
				break
			}
		}
	}
	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*6
	
	const C = 50
	
	pos := 0
	smps := make([][]int, n)
	tmpScore := make([]int, n+1)

	for {
		select {
			case <-ch:
				return
			default:
		}
		if len(smps[pos]) == 0 {
			if pos == 0 {
				nums, ent := enterable(keepout(ra[0][0], 0, target))
				smps[0] = samples(C, nums, ent)
			} else {
				pos--
				continue
			}
		}
		x[0][pos] = smps[pos][0]
		smps[pos] = smps[pos][1:]
		tmp := max(tmpScore[pos], diff(ra[0][pos], x[0][pos]))
		for py,px := 0, pos; px > 0; py,px = py+1,px-1 {
			x[py+1][px-1] = (x[py][px-1]+x[py][px])%M
			tmp = max(tmp, diffe(ra, x, py+1, px-1))
		}
		if tmp >= score {
			continue
		}
		next := pos + 1
		tmpScore[next] = tmp
		if next == n {
			if tmpScore[n] < score {
				score = tmpScore[n]
				copy(ans, x[0][:])
				target = min(target, score - M/100)
			}
			for pos > 0 && tmpScore[pos] >= score {
				smps[pos] = nil
				pos--
			}
			continue
		}
		x[0][next] = 0
		kps := keepout(ra[0][next], x[0][next], target)
		for py,px := 0, next; 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)...)
		}
		nums, ent := enterable(kps)
		smps[next] = samples(C, nums, ent)
		if len(smps[next]) == 0 {
			continue
		}
		pos = next
	}
	
	return
}
0