結果

問題 No.5021 Addition Pyramid
ユーザー ID 21712
提出日時 2025-02-26 02:16:19
言語 Go
(1.23.4)
結果
AC  
実行時間 1,547 ms / 2,000 ms
コード長 2,677 bytes
コンパイル時間 12,493 ms
コンパイル使用メモリ 248,880 KB
実行使用メモリ 6,820 KB
スコア 46,618,556
最終ジャッジ日時 2025-02-26 02:17:53
合計ジャッジ時間 92,415 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 solve(n int, a [][]int) (ans []int) {
	ans = make([]int, n)
	score := calcScore(n, a, ans)
	for k := 0; k < 1e3; k++ {
		for i, old := range ans {
			for j := 0; j < 5; j++ {
				ans[i] = (ans[i] + rand.Intn(M*4/5)+M/5) % M
				tmp := calcScore(n, a, ans)
				if tmp < score {
					score = tmp
					old = ans[i]
				}
			}
			ans[i] = old
		}
	}
	return
}
0