結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー ID 21712
提出日時 2025-02-28 18:57:45
言語 Go
(1.23.4)
結果
AC  
実行時間 541 ms / 2,000 ms
コード長 3,651 bytes
コンパイル時間 13,008 ms
コンパイル使用メモリ 255,344 KB
実行使用メモリ 6,824 KB
スコア 200,000,000
最終ジャッジ日時 2025-02-28 18:58:15
合計ジャッジ時間 28,749 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

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
	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 solve(n int, a [][]int) (ans []int) {
	
	// うっかりツイッターで解法を目にしてしまった
	// おわりです
	
	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
	
	const Target = M/2-M/100*4
	
outer:
	for q := 0; q < 2e3; q++ {
		x[0][0] = (ra[0][0]+Target)%M
		for i := 1; i < n; i++ {
			bestx, beste := 0, score
			for k := 0; k < 200; k++ {
				x[0][i] = random(ra[0][i], score)
				e := diffe(ra, x, 0, i)
				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
					e = max(e, diffe(ra, x, py+1, px-1))
				}
				if e < beste {
					bestx,beste = x[0][i],e
				}
			}
			if beste >= score {
				continue outer
			}
			x[0][i] = bestx
			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
			}
		}
	}
	return
}
0