2026-10-09
Dice.hs
dice :: Int -> Int -> [[Int]]
n 個のさいころを順に振ったときの目の並び(1から6の整数のリスト)のうち、和が s になるものをすべて返す dice を書いてください。並びは辞書順に並べます。さいころが0個のときは、目のない空の並び1つだけがあり、その和は0です。
入力例 1
dice 2 3
出力例 1
[[1,2],[2,1]]
入力例 2
dice 2 13
出力例 2
[]
入力例 3
dice 0 0
出力例 3
[[]]
Reference
import Control.Monad (replicateM)
dice :: Int -> Int -> [[Int]]
dice n s = filter ((== s) . sum) (replicateM n [1 .. 6])
参考実装は、replicateM n [1 .. 6] で n 個の目の並びをすべて作り、和が s のものだけを filter で残します。リストのモナドの replicateM n xs は xs を n 個掛け合わせた直積で、先頭の要素ほどゆっくり変わる順、つまり辞書順に並びを作るので、並べ替えは要りません。
n が0のとき、replicateM 0 は何も選ばない並び1つだけの [[]] を返します。空の並びの和は0なので、dice 0 0 は [[]]、dice 0 5 は [] です。replicateM 0 xs を [] と取り違えると、ここを間違えます。
並びは全部で6の n 乗通りあるので、n が大きいと時間がかかります。掲載したのは参考実装で、唯一の正解ではありません。1個目の目 d を選んで残りを dice (n - 1) (s - d) に任せる再帰で書き、s が負になった枝をそこで捨てれば、和が合わない並びを最後まで作らずに済みます。