結果

問題 No.1495 パンの仕入れ
ユーザー 草苺奶昔
提出日時 2023-02-28 15:22:53
言語 Go
(1.23.4)
結果
AC  
実行時間 457 ms / 2,000 ms
コード長 3,809 bytes
コンパイル時間 15,147 ms
コンパイル使用メモリ 223,776 KB
実行使用メモリ 24,656 KB
最終ジャッジ日時 2024-09-15 17:34:19
合計ジャッジ時間 29,630 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "bufio"
    "fmt"
    "os"
)
func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var T int
    fmt.Fscan(in, &T)
    for t := 0; t < T; t++ {
        var N, M, K int
        fmt.Fscan(in, &N, &M, &K)
        // 这里的函数 f[i] = sum(Bxi-yi)^2 (1<=i<=M)
        A, B, C := make([]int, N), make([]int, N), make([]int, N)
        for i := 0; i < M; i++ {
            var x, y int
            fmt.Fscan(in, &x, &y)
            x--
            A[x]++
            B[x] -= y * 2
            C[x] += y * y
        }
        funcs := make([]SlopeFunc, N)
        for i := 0; i < N; i++ {
            funcs[i] = NewQuadratic(A[i], B[i], C[i], 0, K)
        }
        coeff := make([]int, N)
        for i := 0; i < N; i++ {
            coeff[i] = 1
        }
        res, _, _ := MinConvexSumUnderLinearConstraint(coeff, funcs, K)
        fmt.Fprintln(out, res)
    }
}
const INF int = 1e18
// !minimize sum(fi(xij) for j in range(1, ki+1) for i in range(1, n+1))
//  k: coefficient of each variable
//  f: convex function
//  c: constraint (sum of all variables)
//  return: (y, [[(x_i, # of such x_i), ... ], ...])
func MinConvexSumUnderLinearConstraint(k []int, f []SlopeFunc, c int) (minimum int, res [][][2]int, ok bool) {
    if len(k) != len(f) {
        panic("len(k) != len(f)")
    }
    lowerSum, upperSum := 0, 0
    for _, func_ := range f {
        lowerSum += func_.getLower()
        upperSum += func_.getUpper()
    }
    if lowerSum > c || upperSum < c {
        return
    }
    n := len(k)
    few, enough := -INF, INF
    for enough-few > 1 {
        slope := few + (enough-few)/2
        cnt := 0
        for i := 0; i < n; i++ {
            tmp := f[i].Slope(slope)
            cnt += tmp * k[i]
            if cnt >= c {
                break
            }
        }
        if cnt >= c {
            enough = slope
        } else {
            few = slope
        }
    }
    res = make([][][2]int, n)
    additional := []int{}
    ctmp := 0
    for i := 0; i < n; i++ {
        xLower := f[i].Slope(few)
        xUpper := f[i].Slope(few + 1)
        ctmp += k[i] * xLower
        res[i] = append(res[i], [2]int{xLower, k[i]})
        if xLower < xUpper {
            additional = append(additional, i)
        }
        minimum += k[i] * f[i].Eval(xLower)
    }
    minimum += (c - ctmp) * (few + 1)
    for len(additional) > 0 {
        i := additional[len(additional)-1]
        additional = additional[:len(additional)-1]
        add := 0
        if c-ctmp > k[i] {
            add = k[i]
        } else {
            add = c - ctmp
        }
        x := res[i][0][0]
        if add != 0 {
            res[i][0][1] -= add
            if res[i][0][1] == 0 {
                res[i] = res[i][:len(res[i])-1]
            }
            res[i] = append(res[i], [2]int{x + 1, add})
            ctmp += add
        }
    }
    ok = true
    return
}
type SlopeFunc interface {
    Slope(s int) int
    Eval(x int) int
    getLower() int
    getUpper() int
}
// ax^2 + bx + c (convex), lower <= x <= upper
type Quadratic struct{ a, b, c, lower, upper int }
func NewQuadratic(a, b, c, lower, upper int) *Quadratic { return &Quadratic{a, b, c, lower, upper} }
func (q *Quadratic) Slope(s int) int {
    if q.a == 0 {
        if q.b <= s {
            return q.upper
        }
        return q.lower
    }
    res := (s + q.a - q.b) / (q.a * 2)
    if res > q.upper {
        return q.upper
    }
    if res < q.lower {
        return q.lower
    }
    return res
}
func (q *Quadratic) Eval(x int) int { return (q.a*x+q.b)*x + q.c }
// f(x) - f(x - 1)
func (q *Quadratic) nextCost(x int) int { return 2*q.a*x - q.a + q.b }
func (q *Quadratic) getLower() int      { return q.lower }
func (q *Quadratic) getUpper() int      { return q.upper }
// x^3 - ax, x >= 0 (convex)
type Cubic struct {
    a, lower, upper int
}
func NewCubic(a, upper int) *Cubic { return &Cubic{a, 0, upper} }
func (c *Cubic) Slope(s int) int {
    lo, hi := c.lower, c.upper+1
    for hi-lo > 1 {
        mid := (lo + hi) / 2
        if c.nextCost(mid) <= s {
            lo = mid
        } else {
            hi = mid
        }
    }
    return lo
}
func (c *Cubic) Eval(x int) int { return (x*x - c.a) * x }
// f(x) - f(x - 1)
func (c *Cubic) nextCost(x int) int { return 3*x*x - 3*x + 1 - c.a }
func (q *Cubic) getLower() int      { return q.lower }
func (q *Cubic) getUpper() int      { return q.upper }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0