D - A Piece of Cake

[hxrxchang]

https://atcoder.jp/contests/abc304/tasks/abc304_d

問題概要

XY平面上に長方形に広がるケーキがある。その上にいくつかいちごが置かれており、座標(p, q)は分かる。
ケーキに縦方向にA回、横方向にB回切れ目が入れられて、(A+1) * (B+1) 個のピースに分割される。
ピースの中でいちごの数が最小のもの、最大のもののいちごの数をそれぞれ求めよ。

解き方

制約的に愚直にシミュレーションしたら間に合わない。
切れ目の位置は分かるので、各いちごがどのピースに属するかは、もっとも近い切れ目(正確に言うと、自分の位置以上の最小の位置にある切れ目)を探すと分かる。
どのピースに何個いちごが属するかが分かれば、その最大値と最小値を求めれば答えになる。
いちごが属していないピースは今までの計算で登場していないので、それがあれば最小値が0になることに注意。

func solve() {
	getInts()
	n := getInt()

	p := make([]int, n)
	q := make([]int, n)
	for i := 0; i < n; i++ {
		in := getInts()
		p[i] = in[0]
		q[i] = in[1]
	}

	lenA := getInt()
	a := getInts()

	lenB := getInt()
	b := getInts()

	type GridItem struct {
		x, y int
	}
	// いちごがどのピースに集められているかを管理する
	strawberriesCnt := make(map[GridItem]int)
	for i := 0; i < n; i++ {
		x := lowerBound(a, p[i])
		y := lowerBound(b, q[i])
		strawberriesCnt[GridItem{x, y}]++
	}


	mini := n
	maxi := 0
	for _, v := range strawberriesCnt {
		mini = min(mini, v)
		maxi = max(maxi, v)
	}

	// いちごが乗っていないピースがある場合は、最小値は0
	if len(maps.Keys(strawberriesCnt)) < (lenA + 1) * (lenB + 1) {
		mini = 0
	}

	fmt.Println(mini, maxi)
}

https://atcoder.jp/contests/abc304/submissions/60615810