2026-09-03
TernaryMax.hs
ternaryMax :: (Int -> Int) -> Int -> Int -> Int
f は区間 [lo, hi] の上で、ある p までは狭義に増加し、p からは狭義に減少する関数です(p が区間の端でもかまいません)。区間を3つに分けて片側を捨てることを繰り返し、f x が最大になる x、つまり p を返す ternaryMax f lo hi を書いてください。lo は hi 以下で、lo == hi のときは lo を返します。
入力例 1
ternaryMax (\x -> negate (abs (x - 7))) 0 20
出力例 1
7
入力例 2
ternaryMax id 0 9
出力例 2
9
入力例 3
ternaryMax (\x -> x * (10 - x)) 5 5
出力例 3
5
Reference
ternaryMax :: (Int -> Int) -> Int -> Int -> Int
ternaryMax f lo hi
| hi - lo < 3 = snd (maximum [(f x, x) | x <- [lo .. hi]])
| f m1 < f m2 = ternaryMax f (m1 + 1) hi
| otherwise = ternaryMax f lo (m2 - 1)
where
m1 = lo + (hi - lo) `div` 3
m2 = hi - (hi - lo) `div` 3
m1 と m2 で区間を3つに分けます。f m1 < f m2 なら、p は m1 より右にあります。p が m1 以下なら m1 から m2 までは下り坂で、f m1 の方が大きくなるはずだからです。そこで m1 までを捨てます。f m1 >= f m2 なら、同じ理由で p は m2 より左にあるので、m2 から先を捨てます。
幅が3未満になったら分けるのをやめ、残った高々3点を直接比べます。この終了条件がないと、幅が 0 の区間では m1 も m2 も lo になり、m2 - 1 で区間が空になります。捨てる側を ternaryMax f lo m2 のように m2 自身を残す形で書いた場合は、幅が 2 のとき (hi - lo) `div` 3 が 0 で m2 = hi となり、f m1 >= f m2 なら区間が縮まずに同じ呼び出しを繰り返します。
snd (maximum [(f x, x) | ...]) は、(値, 位置) の組を値で比べ、最大の組から位置を取り出します。掲載したのは参考実装で、唯一の正解ではありません。Data.List の maximumBy と Data.Ord の comparing を使い、maximumBy (comparing f) [lo .. hi] と書いても同じ位置が返ります。