Namaran

Code daily. Without assist.

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 が負になった枝をそこで捨てれば、和が合わない並びを最後まで作らずに済みます。