Namaran

Code daily. Without assist.

2026-11-18

Intervals.hs

intervals :: Int -> [(Int, Int)]

0 から n - 1 までの番号について、i <= j となる区間 (i, j) をすべて、短い区間から順に並べたリストを返す intervals を書いてください。区間の長さ j - i が同じものどうしは、i の小さい順に並べます。n が 0 なら空リストを返します。

入力例 1

intervals 3

出力例 1

[(0,0),(1,1),(2,2),(0,1),(1,2),(0,2)]

入力例 2

intervals 1

出力例 2

[(0,0)]

入力例 3

intervals 0

出力例 3

[]
Reference

Reference

intervals :: Int -> [(Int, Int)]
intervals n =
  [ (i, i + d)
  | d <- [0 .. n - 1]
  , i <- [0 .. n - 1 - d]
  ]

リスト内包表記に生成器を2つ並べると、先に書いた生成器が外側のループ、後に書いた生成器が内側のループになります。参考実装は、外側で長さ d を 0 から n - 1 まで動かし、内側で始点 i を動かして (i, i + d) を作ります。d が1つ決まるたびに、その長さの区間を i の小さい順に出し切ってから次の長さへ進むので、短い区間から順に並びます。掲載したのは参考実装で、唯一の正解ではありません。

内側の上限 n - 1 - d は、終点 i + d が n - 1 を超えない最大の始点です。入力例 1 では d = 0 で3個、d = 1 で2個、d = 2 で1個の区間が出ます。n が 0 のときは [0 .. -1] が空なので、外側の生成器が値を1つも出さず、空リストになります。生成器を i、d の順に書くと、始点ごとにまとまった [(0,0),(0,1),(0,2),(1,1),…] になってしまいます。

区間DPで表を下から埋めるときは、この順に計算すれば、区間 (i, j) を分けた左右の区間はどちらもそれより短いので、すでに値が入っています。