結果

問題 No.5020 Averaging
ユーザー ID 21712ID 21712
提出日時 2024-10-25 14:27:28
言語 Go
(1.22.1)
結果
AC  
実行時間 752 ms / 1,000 ms
コード長 9,915 bytes
コンパイル時間 12,268 ms
コンパイル使用メモリ 245,488 KB
実行使用メモリ 26,864 KB
スコア 29,917,268
最終ジャッジ日時 2024-10-25 14:28:18
合計ジャッジ時間 47,231 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 565 ms
22,380 KB
testcase_01 AC 581 ms
22,284 KB
testcase_02 AC 622 ms
24,560 KB
testcase_03 AC 707 ms
24,632 KB
testcase_04 AC 715 ms
24,716 KB
testcase_05 AC 678 ms
24,640 KB
testcase_06 AC 493 ms
22,160 KB
testcase_07 AC 687 ms
22,392 KB
testcase_08 AC 647 ms
24,592 KB
testcase_09 AC 568 ms
22,324 KB
testcase_10 AC 497 ms
20,224 KB
testcase_11 AC 700 ms
24,720 KB
testcase_12 AC 673 ms
24,680 KB
testcase_13 AC 703 ms
24,712 KB
testcase_14 AC 717 ms
24,624 KB
testcase_15 AC 631 ms
22,420 KB
testcase_16 AC 752 ms
26,864 KB
testcase_17 AC 693 ms
22,540 KB
testcase_18 AC 559 ms
22,236 KB
testcase_19 AC 596 ms
22,220 KB
testcase_20 AC 683 ms
24,504 KB
testcase_21 AC 514 ms
22,180 KB
testcase_22 AC 671 ms
22,372 KB
testcase_23 AC 716 ms
24,620 KB
testcase_24 AC 677 ms
22,528 KB
testcase_25 AC 636 ms
22,408 KB
testcase_26 AC 567 ms
20,240 KB
testcase_27 AC 623 ms
22,328 KB
testcase_28 AC 663 ms
24,588 KB
testcase_29 AC 690 ms
24,644 KB
testcase_30 AC 591 ms
20,236 KB
testcase_31 AC 597 ms
22,500 KB
testcase_32 AC 595 ms
22,532 KB
testcase_33 AC 564 ms
22,460 KB
testcase_34 AC 673 ms
22,380 KB
testcase_35 AC 711 ms
23,624 KB
testcase_36 AC 722 ms
24,624 KB
testcase_37 AC 642 ms
24,452 KB
testcase_38 AC 704 ms
24,660 KB
testcase_39 AC 524 ms
22,236 KB
testcase_40 AC 704 ms
22,392 KB
testcase_41 AC 745 ms
26,804 KB
testcase_42 AC 664 ms
22,524 KB
testcase_43 AC 662 ms
22,528 KB
testcase_44 AC 665 ms
24,604 KB
testcase_45 AC 558 ms
22,224 KB
testcase_46 AC 632 ms
24,620 KB
testcase_47 AC 568 ms
20,156 KB
testcase_48 AC 696 ms
24,608 KB
testcase_49 AC 663 ms
22,428 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

func main() {
	var input string
	Scan(&input)
	if input == "LOCAL" {
		runLocal()
		return
	}
	var n int
	Sscan(input, &n)
	a := make([]int64, n, n)
	b := make([]int64, n, n)
	for i := range a {
		Scan(&a[i], &b[i])
	}
	s := NewSolver(n, a, b)
	s.Solve()
	u, v := s.Answer()
	if err := check(n, u, v); err != nil {
		if err == errZeroIndexed {
			fixIndex(u, v)
		} else {
			Println(err)
			panic(err)
		}
	}
	output(u, v)
}

func output(u, v []int) {
	Println(len(u))
	for i, ui := range u {
		Println(ui, v[i])
	}
}

func fixIndex(u, v []int) {
	isZeroIndexed := false
	for i, ui := range u {
		if ui == 0 || v[i] == 0 {
			isZeroIndexed = true
			break
		}
	}
	if isZeroIndexed {
		for i := range u {
			u[i]++
			v[i]++
		}
	}
}

const (
	N     = 45
	ABmax = int64(1e18)
	ABmin = int64(1e17)
	X     = 50
	Base  = int64(5e17)
	Seed  = 12121212
)

func generate(n int, seed int64) (a, b []int64) {
	a = make([]int64, n, n)
	b = make([]int64, n, n)
	r := rand.New(rand.NewSource(seed))
	for i := range a {
		a[i] = r.Int63n(ABmax-ABmin) + ABmin
	}
	for i := range b {
		b[i] = r.Int63n(ABmax-ABmin) + ABmin
	}
	return
}

var errZeroIndexed = Errorf("ErrZeroIndexed")

func check(n int, u, v []int) error {
	if len(u) != len(v) {
		return Errorf("<<<WA>>> len(u)=%d != len(v)=%d ", len(u), len(v))
	}
	if len(u) > X {
		return Errorf("<<<WA>>> len(u) > %d", len(u), X)
	}
	if len(u) == 0 {
		return nil
	}
	min, max := n, 0
	for i, ui := range u {
		if ui == v[i] {
			return Errorf("<<<WA>>> u[%d]=%d == v[%d]=%d", i, ui, i, v[i])
		}
		if ui < min {
			min = ui
		}
		if v[i] < min {
			min = v[i]
		}
		if ui > max {
			max = ui
		}
		if v[i] > max {
			max = v[i]
		}
	}
	if !((min == 0 && max < n) || (min == 1 && max <= n)) {
		return Errorf("<<<WA>>> min(u,v)=%d, max(u,v)=%d", min, max)
	}
	if min == 0 {
		return errZeroIndexed
	}
	return nil
}

func show(n int, a, b []int64) {
	Println("N =", n)
	for i, ai := range a {
		Printf("A[%2d] = %19d, B[%2d] = %19d\n", i, ai, i, b[i])
	}
}

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

func max(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

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

func process(n int, a, b []int64, u, v []int) {
	ta := make([]int64, n, n)
	tb := make([]int64, n, n)
	copy(ta, a)
	copy(tb, b)
	a, b = nil, nil
	Println("Len = ", len(u))
	for i, ui := range u {
		vi := v[i]
		Printf("u[%2d] = %2d, v[%2d] = %2d\n", i, ui, i, vi)
		Printf("    A[%2d] = %19d, B[%2d] = %19d\n", ui, ta[ui], ui, tb[ui])
		Printf("    A[%2d] = %19d, B[%2d] = %19d\n", vi, ta[vi], vi, tb[vi])
		aa, bb := (ta[ui]+ta[vi])/2, (tb[ui]+tb[vi])/2
		Printf("    A[**] = %19d, B[**] = %19d\n", aa, bb)
		da, db := abs(aa-Base), abs(bb-Base)
		Printf("     diff = %19d,  diff = %19d\n", da, db)
		Printf("     max  = %19d,  len  = %2d\n", max(da, db), len(Sprint(max(da, db))))
		ta[ui], tb[ui] = aa, bb
		ta[vi], tb[vi] = aa, bb
	}
	va, vb := abs(ta[0]-Base), abs(tb[0]-Base)
	Printf("V(A) = %19d, V(B) = %19d\n", va, vb)
	Printf(" max = %19d, len  = %2d\n", max(va, vb), len(Sprint(max(va, vb))))
	score := int64(2e6) - int64(1e5*math.Log10(float64(max(va, vb)+1)))
	if max(va, vb) == 0 {
		score += X - int64(len(u))
	}
	Printf("SCORE = %7d, SCORE*50 = %9d\n", score, score*50)
}

func runLocal() {
	var n int = N
	var seed int64 = Seed
	Scan(&n, &seed)
	a, b := generate(n, seed)
	show(n, a, b)
	t := time.Now()
	s := NewSolver(n, a, b)
	s.Solve()
	u, v := s.Answer()
	Println(time.Since(t))
	Println(s.info)
	if err := check(n, u, v); err != nil {
		if err != errZeroIndexed {
			Println(err)
			panic(err)
		}
	}
	process(n, a, b, u, v)
}

type Solver struct {
	n    int
	a, b []int64
	u, v []int
	info string
}

func NewSolver(n int, a, b []int64) *Solver {
	ta := make([]int64, n, n)
	tb := make([]int64, n, n)
	copy(ta, a)
	copy(tb, b)
	return &Solver{n, ta, tb, []int{}, []int{}, ""}
}

func (s *Solver) Clone() *Solver {
	ta := make([]int64, s.n, s.n)
	tb := make([]int64, s.n, s.n)
	copy(ta, s.a)
	copy(tb, s.b)
	return &Solver{s.n, ta, tb, []int{}, []int{}, ""}
}

func (s *Solver) Answer() (u, v []int) {
	return s.u, s.v
}

func (s *Solver) score() int64 {
	return max(abs(s.a[0]-Base), abs(s.b[0]-Base))
}

func (s *Solver) Solve() {
	if s.n != N {
		s.greedy()
		return
	}
	t := s.Clone()
	t.dp()
	if t.score() < s.score() {
		s.u, s.v = t.u, t.v
	}
}

func (s *Solver) goodluck() *Solver {
	var best *Solver
	{
		g := s.Clone()
		g.info = "greedy"
		g.greedy()
		best = g
	}
	for p := 4; p <= 32; p *= 2 {
		t := s.Clone()
		t.info = Sprint("greedy&average(", p, ")")
		if !t.greedy() || len(s.u)+p+1 >= X {
			continue
		}
		if err := t.average(p); err != nil {
			continue
		}
		if t.greedy() {
			t.info += "&greedy"
		}
		if t.score() < best.score() {
			best = t
		}
	}
	for p := 4; p <= 32; p *= 2 {
		for i := 0; i < 100; i++ {
			t := s.Clone()
			t.info = Sprint("avarage(", p, ")")
			t.average(p)
			if t.greedy() {
				t.info += "&greedy"
			}
			if t.score() < best.score() {
				best = t
			}
		}
	}
	for p := 4; p <= 32; p *= 2 {
		for sz := 10; sz+p < X-2; sz++ {
			for i := 0; i < 100; i++ {
				t := s.Clone()
				t.info = Sprint("random(", sz, ")&avarage(", p, ")")
				t.random(sz)
				if err := t.average(p); err != nil {
					continue
				}
				if t.greedy() {
					t.info += "&greedy"
				}
				if t.score() < best.score() {
					best = t
				}
			}
		}
	}
	for sz := 15; sz < X; sz++ {
		for i := 0; i < 2000; i++ {
			t := s.Clone()
			t.info = Sprint("random(", sz, ")")
			t.random(sz)
			if t.greedy() {
				t.info += "&greedy"
			}
			if t.score() < best.score() {
				best = t
			}
		}
	}
	return best
}

func (s *Solver) greedy() bool {
	before := len(s.u)
	for i := len(s.u); i < X; i++ {
		best := s.score()
		zk := -1
		for k := 1; k < s.n; k++ {
			aa := (s.a[0] + s.a[k]) / 2
			bb := (s.b[0] + s.b[k]) / 2
			s := max(abs(aa-Base), abs(bb-Base))
			if s < best {
				best, zk = s, k
			}
		}
		if zk < 0 {
			break
		}
		s.u = append(s.u, 0)
		s.v = append(s.v, zk)
		aa := (s.a[0] + s.a[zk]) / 2
		bb := (s.b[0] + s.b[zk]) / 2
		s.a[0], s.b[0] = aa, bb
		s.a[zk], s.b[zk] = aa, bb
	}
	return before != len(s.u)
}

// size .. 2,4,8,16,32
func (s *Solver) average(size int) error {
	switch size {
	default:
		return Errorf("wrong size %d", size)
	case 2, 4, 8, 16, 32:
		if len(s.u)+size+1 >= X {
			return Errorf("over")
		}
	}
	const Div = 100
	target := (Base / Div) * int64(size)
	idx := rand.Perm(N)
	for i, x := range idx {
		if x == 0 {
			idx[0], idx[i] = idx[i], idx[0]
			break
		}
	}
	var sumA, sumB int64
	for _, i := range idx[:size] {
		sumA += s.a[i] / Div
		sumB += s.b[i] / Div
	}
	best := max(abs(sumA-target), abs(sumB-target))
	for {
		update := 0
		for i := 1; i < size; i++ {
			ii := idx[i]
			sumA -= s.a[ii] / Div
			sumB -= s.b[ii] / Div
			xk := -1
			for k := size; k < N; k++ {
				ik := idx[k]
				sumA += s.a[ik] / Div
				sumB += s.b[ik] / Div
				v := max(abs(sumA-target), abs(sumB-target))
				if v < best {
					best, xk = v, k
				}
				sumA -= s.a[ik] / Div
				sumB -= s.b[ik] / Div
			}
			if xk < 0 {
				sumA += s.a[ii] / Div
				sumB += s.b[ii] / Div
			} else {
				ik := idx[xk]
				sumA += s.a[ik] / Div
				sumB += s.b[ik] / Div
				idx[i], idx[xk] = ik, ii
				update++
			}
		}
		if update == 0 {
			break
		}
	}
	for p := 1; p < size; p *= 2 {
		for i := 0; i < size; i += p * 2 {
			ii, ip := idx[i], idx[i+p]
			s.u = append(s.u, ii)
			s.v = append(s.v, ip)
			aa := (s.a[ii] + s.a[ip]) / 2
			bb := (s.b[ii] + s.b[ip]) / 2
			s.a[ii], s.b[ii] = aa, bb
			s.a[ip], s.b[ip] = aa, bb
		}
	}
	return nil
}

func (s *Solver) random(size int) {
	for ; size > 0; size-- {
		x := rand.Intn(s.n)
		y := (x + rand.Intn(s.n-1) + 1) % s.n
		s.u = append(s.u, x)
		s.v = append(s.v, y)
		aa := (s.a[x] + s.a[y]) / 2
		bb := (s.b[x] + s.b[y]) / 2
		s.a[x], s.b[x] = aa, bb
		s.a[y], s.b[y] = aa, bb
	}
}

func (s *Solver) dp() {
	const (
		Div  = 100
		Vmax = 1e4
	)

	type State struct {
		c                int
		flag, sumA, sumB int64
	}
	score := func(st *State) int64 {
		a := abs(st.sumA - Base/Div*int64(st.c))
		b := abs(st.sumB - Base/Div*int64(st.c))
		return max(a, b)
	}
	index := func(st *State) int {
		return int(score(st) / (Base / Div * int64(st.c) / Vmax))
	}
	add := func(st *State, x int) *State {
		if st == nil {
			return &State{
				c:    1,
				flag: 1 << uint(x),
				sumA: s.a[x] / Div,
				sumB: s.b[x] / Div,
			}
		} else {
			return &State{
				c:    st.c + 1,
				flag: st.flag | (1 << uint(x)),
				sumA: st.sumA + s.a[x]/Div,
				sumB: st.sumB + s.b[x]/Div,
			}
		}
	}
	better := func(st1, st2 *State) *State {
		if st1 == nil {
			return st2
		} else if st2 == nil {
			return st1
		} else if score(st1)/int64(st1.c) < score(st2)/int64(st2.c) {
			return st1
		} else {
			return st2
		}
	}

	dp := make([][]*State, 33)
	for i := range dp {
		dp[i] = make([]*State, Vmax+1)
	}

	first := add(nil, 0)
	dp[1][index(first)] = first

	for x := 1; x < N; x++ {
		for i := 31; i > 0; i-- {
			for _, e := range dp[i] {
				if e == nil {
					continue
				}
				st := add(e, x)
				idx := index(st)
				dp[i+1][idx] = better(dp[i+1][idx], st)
			}
		}
	}

	xx := []*State{}
	for i := 2; i <= 32; i *= 2 {
		for _, e := range dp[i] {
			if e != nil {
				xx = append(xx, e)
			}
		}
	}
	Slice(xx, func(i, j int) bool {
		return score(xx[i])/int64(xx[i].c) < score(xx[j])/int64(xx[j].c)
	})
	best := xx[0]

	pp := make([]int, 0, best.c)
	for i := 0; i < N; i++ {
		if best.flag&(1<<uint(i)) != 0 {
			pp = append(pp, i)
		}
	}

	for p := 1; p < best.c; p *= 2 {
		for i := 0; i < best.c; i += p * 2 {
			p1 := pp[i]
			p2 := pp[i+p]
			s.u = append(s.u, p1)
			s.v = append(s.v, p2)
			aa := (s.a[p1] + s.a[p2]) / 2
			bb := (s.b[p1] + s.b[p2]) / 2
			s.a[p1], s.b[p1] = aa, bb
			s.a[p2], s.b[p2] = aa, bb
		}
	}
}
0