2026-11-08
RangeSum.hs
rangeSum :: [(Int, [Int])] -> Int -> Int -> Int
配列を先頭から順に空でない塊に分け、各塊を「その塊の要素の和」と「その塊の要素」の組で表したリスト bs があります。塊の長さはそろっているとは限りません。配列の添字 l 以上 r 未満の要素の和を返す rangeSum bs l r を書いてください。区間がまるごと含む塊は、要素を足し直さずに記録してある和を使います。0 <= l <= r <= 配列の長さとし、l == r なら0を返します。
入力例 1
rangeSum [(9, [5, 4]), (10, [1, 2, 7]), (6, [6])] 1 4
出力例 1
7
入力例 2
rangeSum [(9, [5, 4]), (10, [1, 2, 7]), (6, [6])] 2 2
出力例 2
0
入力例 3
rangeSum [(9, [5, 4]), (10, [1, 2, 7]), (6, [6])] 0 6
出力例 3
25
Reference
Reference
rangeSum :: [(Int, [Int])] -> Int -> Int -> Int
rangeSum bs l r = prefix r bs - prefix l bs
prefix :: Int -> [(Int, [Int])] -> Int
prefix _ [] = 0
prefix i ((s, ys) : rest)
| i >= length ys = s + prefix (i - length ys) rest
| otherwise = sum (take i ys)
区間の両端をそのまま扱うと、l の塊の端数、間にある塊、r の塊の端数を分けて足すことになり、l と r が同じ塊に入るときや、間に塊が1つも無いときを別に扱わなければなりません。塊の長さがそろっていないので、添字を割り算して塊の番号を求めることもできません。そこで、添字 l 以上 r 未満の和を、先頭から r 個の和から先頭から l 個の和を引いたものとして求めます。先頭から i 個の和を返す prefix は区間の端が片方しか無いので、塊を先頭から見て、i 個に収まる塊は記録した和 s を足して残りの個数を減らし、収まらない塊に来たらその中の先頭 i 個だけを足す、という1通りの書き方で済みます。これは参考実装で、唯一の正解ではありません。
入力例1の prefix 4 は、長さ2の最初の塊が4個に収まるので9を足し、残り2個を次の塊で数えます。長さ3の次の塊には収まらないので、その先頭2個の1 + 2を足して12です。prefix 1 は最初の塊の先頭1個の5なので、rangeSum は12 - 5 = 7を返します。入力例2は同じ prefix 2 どうしの差なので0です。入力例3の prefix 6 は3つの塊すべてが収まって9 + 10 + 6 = 25になり、prefix 0 は最初の塊の先頭0個で0です。i がちょうど塊の境目に来たときは i >= length ys が成り立つので、その塊は記録した和で足され、次の塊の先頭0個として0が足されます。length ys は要素を数えるだけで足し直しはしませんが、塊の長さも記録しておけば、まるごと含む塊の要素はまったくたどらずに済みます。