Namaran

Code daily. Without assist.

2026-09-24

Visited.hs

visited :: Int -> [Int]

ビットDPの状態でよく使うビットマスクmaskを、実際に訪問済みの都市番号のリストへ変換するvisitedを書いてください。ビットiが立っていれば都市iは訪問済みで、リストは昇順です。ビットが1つも立っていなければ空リストです(境界: 訪問済みが1つもない)。visited 5 → [0, 2](5 = 0b101)、visited 0 → [](境界)、visited 7 → [0, 1, 2](7 = 0b111)。

Reference
visited :: Int -> [Int]
visited mask = [i | i <- [0 .. finiteBitSize mask - 1], testBit mask i]

Data.BitsのtestBit mask iは、maskのビットiが立っているかをBoolで返します。finiteBitSize maskはIntが持つビット数(実行環境で決まる定数、多くは64)で、これを使って調べる範囲[0 .. finiteBitSize mask - 1]を決めています。リスト内包表記は0から順にiを試すので、結果のリストは自然に昇順になります。ビットDPでは訪問済みの集合を1つの整数(ビットマスク)として持ち運びますが、その中身を人間が読める形に戻したいとき——たとえばデバッグ出力や、このドリルの解説のように——には、こうして立っているビットの位置を素直に集めるだけで復元できます。これは参考実装であり、唯一の正解ではありません。