002 - Encyclopedia of Parentheses（★3）

2025-10-09

問題

解答

提出 #69927885

type I = Int
type O = [String]

solve :: I -> O
solve n = map (g n) xs
    where
        xs = filter (f n) [0..2^n-1]

g :: Int -> Int -> String
g n x = map (\x -> if x == 0 then '(' else ')') l
    where
        l = bitList n x

f :: Int -> Int -> Bool
f n x = minimum l' >= 0 && last l' == 0
    where
        l = map (\x -> if x == 0 then 1 else (-1)) 
            $ bitList n x
        l' = scanl1 (+) l

bit全探索

ライブラリに追加

bitList :: Int -> Int -> [Int]
bitList digit x = map (`mod` 2) divs
    where
        divs = scanr (\x acc -> acc `div` 2) x $ replicate (digit-1) ()

digit桁の整数xのビット列を、0|1のリストで返す。Boolのリストで返した方が良い？要調整