HaskellでABC426を解く

はじめに

今回はC問題で初めて使う関数の使い方でちょっと手こずってしまいました。Dは解き方分からず。

A問題

if-then-elseで強引にやろうかとも思ったがそれはそれで間違いそうなのでIntMapで辞書を用意して回答するようにしました。たまにTYPOでA問題間違うこともあるので問題文からコピーしてTYPOを回避。

ABC426A.hs

main = do
  [x,y] <- words <$> getLine
  let m = M.fromList $ zip ["Ocelot", "Serval", "Lynx"] [3,2,1]
  let x' = conv m x
  let y' = conv m y
  putStrLn $ if x' <= y' then "Yes" else "No"

conv m x = i
  where
    i = m M.! x

提出

https://atcoder.jp/contests/abc426/submissions/69837185

B問題

B問題はAより簡単でほぼワンライナーでかけます。

ABC426B.hs

main = do
  s <- getLine
  let ans = snd $ head $ sort $ map (\g -> (length g, head g)) $ group $ sort s
  putStrLn [ans]

提出

https://atcoder.jp/contests/abc426/submissions/69840675

C問題

IntMapで同じOSが何個あるかを管理するようにしておいて、あるキーより小さいの成分を移動させるようにした。キーより小さいものキーと同じものキーより大きいもので要素を分けるのにsplitLookupを使用した。ただこの関数キーと同じ要素があったりなかったりする部分がちょっと扱いづらいと感じた。
splitLookup関数は O(min(n,W)) のアルゴリズムなので時間間に合うかちょっと心配でしたが時間は余裕でした。

ABC426C.hs

main = do
  [n,q] <- readInts
  xys <- replicateM q $ do
    [x,y] <- readInts
    return (x,y)
  let m = M.fromList $ zip [1..n] (repeat 1)
  putStr $ unlines $ map show $ solve m xys

solve _ [] = []
solve m ((x,y):xys)
  | isJust m2 = (cnt1+cnt2) : solve m5 xys
  | isNothing m2 = cnt1 : solve m4 xys
  | otherwise = 0 : solve m xys
  where
    (m1,m2,m3) = M.splitLookup x m
    acs = M.assocs m1 :: [(Int,Int)]
    m4 = foldl (\acc (_,b) -> M.adjust (+b) y acc) m3 acs :: M.Map Int Int
    m5 = M.insertWith (+) y (fromJust m2) m4
    cnt1 = sum $ map snd acs
    cnt2 = fromJust m2

提出

https://atcoder.jp/contests/abc426/submissions/69862303

提出（コンテスト終了後）

解説を見て解き直しました。解説の解き方は最初考えた解き方とほぼ同じなんですがMutableな配列を使うとコンテスト中はハマりやすいのもありこのやり方は採用しませんでした。
https://atcoder.jp/contests/abc426/submissions/69891822

D問題

コンテスト中は解法思いつけませんでしたが解説を読んであっさり解けることがわかりました。

ABC426D.hs

main = do
  t <- readLn :: IO Int
  replicateM_ t $ do
    n <- readLn :: IO Int
    s <- getLine
    print $ min (makeOnes n s) (makeZeros n s)

countBase n s cTarget cSub = subs + (targets - noCounts) * 2
  where
    targets = length $ filter (==cTarget) s
    subs = n - targets
    targetNoCounts = map snd $ filter ((==cTarget).fst) $ map (\g -> (head g, length g)) $ group s
    noCounts = if null targetNoCounts then 0 else maximum targetNoCounts

makeOnes n s = countBase n s '1' '0'
makeZeros n s = countBase n s '0' '1'

提出(コンテスト終了後)

https://atcoder.jp/contests/abc426/submissions/69892246

おわりに

今週はCまで。最近のDは解けそうで解けない状況が続いてましたが今回のD問題はまったく解き方分からずでした。