001 - Yokan Party（★4）

2025-10-13

問題

解答

提出 #70120367

type I = [[Int]]
type O = Int

solve :: I -> O
solve [[n,l],[k],as] = ans
    where
        ans = binSearch (f ds k) 0 l
        ds = zipWith (-) (as ++ [l]) (0:as)

f :: [Int] -> Int -> Int -> Bool
f ds k x = f' ds (k+1) 0
    where
        f' as 0 acc = True
        f' [] k' acc = False
        f' (a:as) k' acc
            | acc + a >= x = f' as (k'-1) 0
            | otherwise = f' as k' (acc + a)

答えを二分探索でみつける。fは、ようかんを長さx以上のk+1個のピースに分割できるか判定する関数。

ライブラリに追加

binSearch :: (Int -> Bool) -> Int -> Int -> Int
binSearch f left right = lowerBound (not. f) left right True - 1

(left, right]の範囲で、f x == True になる最大のxを見つける。f x == True を満たす最大のxは、f x == False を満たす最小のxから1引いたもとの等しい。また、True > Falseなので、lowerBoundを使って実装した。