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*t.a