結果

問題 No.3527 Minimum Abs Sum
コンテスト
ユーザー ID 21712
提出日時 2026-05-05 23:46:39
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 232 ms / 2,000 ms
コード長 3,018 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 15,420 ms
コンパイル使用メモリ 294,680 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2026-05-05 23:47:03
合計ジャッジ時間 18,108 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

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

/*
考察

数学ですか…

f(x) = Σ|Ai * x - Bi|
Fi(x) = |Ai * x - Bi| と置く

i番目の Fi(x) = |Ai * x - Bi| に注目すると
Xi = Bi / Ai のときに Fi(Xi) は 0 になって
その 0 の点の Xi より x が小さい領域は 傾き -|Ai| の直線（1次関数）、
その 0 の点の Xi より x が大きい領域は 傾き |Ai| の直線（1次関数）
その 0 の点を底にしたV字の関数グラフになっている

入力の数列を
Xi = Bi / Ai で昇順ソートした i の並び順を p0 ... pk ... pn (k = 0...n) で表すと
（考察の便宜のため N 個の Xi は相異なるとする）
（考察の便宜のため N 個すべて Ai != 0 とする）

ある点 Xpk に注目したときf(x) の増減（微分）を考えると
Xpk-1 < x < Xpk の領域の f(x) の増減は = (|Ap0| + ... + |Apk-1|) - (|Apk| + |Apk+1| + ... + |Apn|)
Xpk < x < Xpk+1 の領域の f(x) の増減は = (|Ap0| + ... + |Apk-1| + |Apk|) - (|Apk+1| + ... + |Apn|)
増減が負の値から正の値に反転する極小値がただ1つ存在するはずで、そこが本問の最小値に相当すると思われる

つまり、Xi でソートして増減の累積和を取りながら増減が反転する箇所を見つければよいことになる

上記の考察では Xi が相異なるとしたが同値の要素も存在する可能性がある
その場合でも増減の反転の検出位置はたぶん問題ないはず
仮に Xpk-1, Xpk, Xpk+1 が同値だったとして Apk-1,Apk,Apk+1 のいずれかの増減の変化で反転しても最小の x は変わらない

Ai = 0 のときは Fi(x) は定数項であり、無視してよいやつ
 f(x) の最小値を求めるのではなく、 f(x) が最小値となる x を求める問題なので
Ai = 0 の要素は x の特定に寄与しない
*/

type P struct { a, b int }

func (p *P) Less(t *P) bool {
	return p.b*sign(p.a)*abs(t.a)<t.b*sign(t.a)*abs(p.a) // WAの理由 もしかして 両辺に負数掛けると不等号逆になる配慮忘れ？
}

func sign(a int) int {
	switch {
		case a < 0:
			return -1
		case a > 0:
			return 1
		default:
			return 0
	}
}

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

const M int = 1e9+7

var mi = NewInt(int64(M))

func mod(a int) int {
	return (M+a%M)%M
}

func inv(a int) int {
	return int(new(Int).ModInverse(NewInt(int64(a)), mi).Int64())
}

func main() {
	rd:=bf.NewReader(Stdin)
	var n int
	Fscan(rd,&n)
	ps := make([]*P, n)
	for i := range ps {
		ps[i] = new(P)
		Fscan(rd,&ps[i].a)
	}
	for _, p := range ps {
		Fscan(rd,&p.b)
	}
	Slice(ps, func(i, j int) bool {
		return ps[i].Less(ps[j])
	})
	sum := 0
	for _, p := range ps {
		sum -= abs(p.a)
	}
	for _, p := range ps {
		sum += 2*abs(p.a) // REの理由 abs 忘れ
		if sum < 0 {
			continue
		}
		ans := mod(p.b)*inv(mod(p.a))%M
		Println(ans)
		return
	}
	panic("考察ミス")
}
0