結果

問題 No.1251 絶対に間違ってはいけない最小化問題
コンテスト
ユーザー ID 21712
提出日時 2026-06-01 03:46:56
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 288 ms / 2,000 ms
コード長 3,235 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,399 ms
コンパイル使用メモリ 277,340 KB
実行使用メモリ 34,304 KB
最終ジャッジ日時 2026-06-01 03:47:30
合計ジャッジ時間 30,215 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"
import . "sort"
import "math/rand"

func main() {
	rd := bf.NewReader(Stdin)
	
	var n int
	Fscan(rd,&n)
	a := make([]int, n)
	for i := range a {
		Fscan(rd,&a[i])
	}
	b := make([]int, n)
	for i := range b {
		Fscan(rd,&b[i])
	}
	
	x, fx := solve2(n, a, b)
	Println(x, fx)
}

func abs(a int) int {
	return max(a, -a)
}

func solve1(n int, a, b []int) (int, int) {
	table := make([]int, 2e6+1)
	s, t := 0, 0
	f := 0
	for i := 0; i < n; i++ {
		table[a[i]+1e6] += b[i]
		f += b[i]*abs(a[i]-(-1e6))
		t += b[i]
	}
	xMin := int(-1e6)
	fMin := f
	for x := xMin; x < 1e6; x++ {
		e := table[x+1e6]
		s += e
		t -= e
		f += s - t
		if f < fMin {
			xMin = x+1
			fMin = f
		}
	}
	return xMin, fMin
}

func solve2(n int, a, b []int) (int, int) {
	index := make([]int, n)
	for i := range index {
		index[i] = i
	}
	Slice(index, func(i, j int) bool {
		return a[index[i]] < a[index[j]]
	})
	s, t := 0, 0
	for _, e := range b {
		t += e
	}
	for _, i := range index {
		s += b[i]
		t -= b[i]
		if s >= t {
			x := a[i]
			f := 0
			for k := 0; k < n; k++ {
				f += b[k] * abs(a[k] - x)
			}
			return x, f
		}
	}
	return 0,0
}

func init() {
	check()
}

func check() {
	for t := 0; t < 10; t++ {
		n := rand.Intn(20)+10
		a := make([]int, n)
		for i := range a {
			a[i] = rand.Intn(2*n)-n
		}
		b := make([]int, n)
		for i := range b {
			b[i] = rand.Intn(3)+1
		}
		x1,f1 := solve1(n, a, b)
		x2,f2 := solve2(n, a, b)
		if f1 != f2 {
			println("n=",n)
			println("a=",Sprint(a))
			println("b=",Sprint(b))
			println("x1=",x1)
			println("f1=",f1)
			println("x2=",x2)
			println("f2=",f2)
			panic("wrong")
		}
	}
	println("OK")
}

/*
考察

X = min(A)
としてf(X)を計算する
このとき f(X+1) について考える
すべてのAと差分が 1 だけ変化する
A[i] < X+1 のとこは B[i] だけ増える 
A[i] >= X+1 のとこは B[i] だけ減る

つまり、適当な X をとって +1 すると
A[i] < X+1 な位置にあるものに対応する B[i] の合計の分だけ f が増える
A[i] >= X+1 な位置にあるもに対応する B[i] の合計の分だけ f が減る
前者のB[i]の合計をS、後者のB[i]の合計をT、とすると
Xを+1すると、fはS増えて、fはT減る、
Xがある点A[i]に到達するとS,Tが変化し SはB[i]増えて、TはB[i]減る
S < T になる X の領域は f は減少して　（X=min(A)はこの領域かも）
S = T になる X の領域は f は変化せず　
S > T になる X の領域は f は増加する　（X=max(A)はこの領域かも）
つまり
S < T から S > T にかわるあたりがfを最小にするXの位置
S = T の領域が存在すればその領域のどこでもfを最小にするXの位置のはず
いずれにせよA[i]のどれかがfを最小にするXとして使える
S=Tとなる領域においては領域内の任意実数をXとしても使えるが、なんの意味が

A[i]は10^6と大きくないため
X=min(A)からX=max(A)までXを+1ずつ動かしてf(X)を変化さて最小を求めるでもいいし

Bの累積和をとって、S,Tの大小関係が逆転する位置X=A[i]を特定してf(X)を計算するでもいいし

そんな感じ？



*/
0