001 - Yokan Party（★4）

https://atcoder.jp/contests/typical90/tasks/typical90_a

問題概要

長さLcmの羊羹があり、N個の切れ目がある。切れ目は A[i]cm の位置につけられている。 K個の切れ目を選び、羊羹をK + 1のピースに分割したい。切った時に最小になるピースを、できるだけ大きくしたい。できるだけ大きくした最小のピースは何cmか。

解き方

最小値の最大化には二分探索 (https://drken1215.hatenablog.com/entry/2021/06/12/020300)

初期値を

left(最小値をその値にできる): -1
right(最小値をその値にできない): L + 1

にして、二分探索していく。

最小値をその値にできるかどうか判定は、Aの切れ目を先頭から見ていき、その値に以上になるように切っていく。切れたピースの個数がK + 1以上だったら、その値にできるということ。

制約は、Lが10 9、Nが100000。計算量は、2分探索に `log2(10 9)、各ステップでNかかるので、log2(10 * 9) 100000` で約3000万回。

var n, l, k int
var a []int

func solve() {
    in := getInts()
    n, l = in[0], in[1]
    k = getInt()
    a = getInts()

    left := -1
    right := l + 1

    for right - left > 1 {
        mid := (left + right) / 2
        if check(mid) {
            left = mid
        } else {
            right = mid
        }
    }

    fmt.Println(left)
}

// aをすべてのピースがlength以上になるように切っていく
// length以上になるピースがk+1個以上になるかどうか
func check(length int) bool {
    cnt := 0
    lastCut := -1
    for i := 0; i < n; i++ {
        var currentLength int
        if lastCut == -1 {
            currentLength = a[i]
        } else {
            currentLength = a[i] - a[lastCut]
        }
        if currentLength >= length {
            cnt++
            lastCut = i
        }
    }
    if lastCut != -1 && l - a[lastCut] >= length {
        cnt++
    }
    return cnt >= k+1
}

https://atcoder.jp/contests/typical90/submissions/54073555

hxrxchang / atcoder

001 - Yokan Party（★4） #68

問題概要

解き方