HaskellでABC462を解く

はじめに

今回はCまで。DはIMOS法を使ってテストケースは通りましたがWAを払拭できずでした。

A問題

フィルターでアルファベット以外を集めます。

A問題提出

main = do
  s <- getLine
  let ans = filter (`notElem` ['a'..'z']) s
  putStrLn ans

B問題

関係の向きを逆にして集計しなおします。

B問題提出

main = do
  n <- readLn :: IO Int
  aas <- replicateM n $ do
    (_:as) <- readInts
    return as
  putStr $ unlines $ solve n aas

solve n aas =  map step3 cands
  where
    bbs = sort $ concatMap step $ zip [1..] aas
    arr = A.accumArray (flip (:)) [] (1,n) bbs :: A.Array Int [Int]
    cands = map (step2 arr) [1..n]

step (i,as) = bs
  where
    bs = map (,i) as

step2 arr i = arr A.! i

step3 xs
  | null xs = "0"
  | otherwise = show (length xs) ++ " " ++ unwords ( map show (sort xs))

C問題

Xを昇順でソートしておいて、Yの最小座標より小さいものがなければそれが求めたいものです。

C問題提出

main = do
  n <- readLn :: IO Int
  xys <- fmap sort <$> replicateM n $ do
    [x,y] <- readInts
    return (x,y)
  print $ snd $ solve $ map snd xys

solve :: [Int] -> (Int,Int)
solve = foldl step (maxBound::Int,0)
  where
    step (y0,cnt) y
      | y < y0 = (y,cnt+1)
      | otherwise = (y0,cnt)

おわりに

D問題の方針は気が付きましたが取りこぼしてしまいました。