#844588 (Go) No.1495 パンの仕入れ

提出ソース

結果

問題	No.1495 パンの仕入れ
ユーザー	草苺奶昔
提出日時	2023-02-28 15:22:53
言語	Go (1.22.1)
結果	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	391 ms 6,940 KB
testcase_03	AC	394 ms 6,400 KB
testcase_04	AC	390 ms 6,400 KB
testcase_05	AC	390 ms 6,400 KB
testcase_06	AC	391 ms 6,528 KB
testcase_07	AC	396 ms 8,100 KB
testcase_08	AC	392 ms 6,400 KB
testcase_09	AC	392 ms 6,944 KB
testcase_10	AC	394 ms 6,940 KB
testcase_11	AC	393 ms 6,528 KB
testcase_12	AC	185 ms 6,144 KB
testcase_13	AC	187 ms 6,272 KB
testcase_14	AC	184 ms 6,144 KB
testcase_15	AC	185 ms 6,272 KB
testcase_16	AC	185 ms 6,272 KB
testcase_17	AC	186 ms 6,272 KB
testcase_18	AC	184 ms 6,144 KB
testcase_19	AC	183 ms 6,144 KB
testcase_20	AC	184 ms 6,144 KB
testcase_21	AC	184 ms 6,144 KB
testcase_22	AC	449 ms 24,444 KB
testcase_23	AC	457 ms 24,448 KB
testcase_24	AC	157 ms 5,760 KB
testcase_25	AC	154 ms 5,760 KB
testcase_26	AC	152 ms 5,760 KB
testcase_27	AC	152 ms 5,760 KB
testcase_28	AC	438 ms 24,508 KB
testcase_29	AC	439 ms 24,656 KB
testcase_30	AC	147 ms 6,016 KB
testcase_31	AC	147 ms 6,016 KB
testcase_32	AC	146 ms 6,144 KB
testcase_33	AC	146 ms 6,144 KB
testcase_34	AC	146 ms 6,016 KB
testcase_35	AC	226 ms 6,144 KB
testcase_36	AC	183 ms 6,272 KB
testcase_37	AC	183 ms 6,272 KB
testcase_38	AC	184 ms 6,144 KB
testcase_39	AC	183 ms 6,272 KB
testcase_40	AC	141 ms 6,144 KB
testcase_41	AC	141 ms 6,016 KB
testcase_42	AC	142 ms 6,144 KB
testcase_43	AC	142 ms 6,144 KB
testcase_44	AC	142 ms 6,144 KB
testcase_45	AC	1 ms 5,376 KB
testcase_46	AC	3 ms 5,376 KB
testcase_47	AC	1 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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 }

yukicoder

結果

テストケース

ソースコード