032 - AtCoder Ekiden (★３)

2025-09-23

問題

解答

提出 #69573877

type I = [[Int]]
type O = Maybe Int

solve :: I -> O
solve ([n]:xs)
    | null iss = Nothing
    | otherwise = Just $ minimum vs
    where
        (as, [m]:ys) = splitAt n xs
        g = nlist2graph n $ map (map (subtract 1)) ys
        iss = filter f . permutations $ [0..n-1]
        f is = and $ zipWith (\a b ->Set.notMember b (g Map.! a)) is (tail is)
        vs = map h iss
        h is = sum $ zipWith (\i j -> (as!!i)!!j) is [0..]

permutations [0..n-1]で走る順番の全パターンを列挙し、filter fで仲が悪いパターンを除去する。その後vs = map h issで各「走る順番」を「ゴールするまでにかかる時間」に変換した。

ライブラリに追加

nlist2graph :: Int -> [[Int]] -> Map.Map Int (Set.Set Int)
nlist2graph n = foldl f initialMap
    where
        initialMap = Map.fromList [(k, Set.empty) | k <- [0..n-1]]
        f mp [xi, yi] = mp''
            where mp' = Map.adjust (Set.insert yi) xi mp
                  mp'' = Map.adjust (Set.insert xi) yi mp'

隣接リストを作る関数nlinst2graphを追加。関数名がしっくりこない。

振り返り

ListやSet、Mapの操作を調べるのに時間がかかった。慣れていきたい

permutations: 順列を列挙

adjust: Mapの特定要素を更新

adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a

notMember: 集合に含まれていない要素であることを確認

notMember :: Ord a => a -> Set a -> Bool