結果

問題 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 }
0