HaskellでABC424を解く

はじめに

今回はC問題で沼から抜け出せす惨敗でした。

A問題

sortして最初の２つか最後の2つが同じ長さなら2等辺三角形と判断。辺の長さに意味があるかをチェックしたが問題の制約で必ず3角形が存在するので2辺の長さがもう1辺よりも長いというチェックはしなくて良かった。

ABC424A.hs

main = do
  [a,b,c] <- sort <$> readInts
  let cond1 = a == b && a + b > c
  let cond2 = b == c && b + c > a
  putStrLn $ bool "No" "Yes" (cond1 || cond2)

提出

https://atcoder.jp/contests/abc424/submissions/69478466

B問題

Mapの成分にSetを持たせる構造で対応。

ABC424B.hs

main = do
  [n,m,k] <- readInts
  abs <- replicateM k $ do
    [a,b] <- readInts
    return (a,b)
  let mp = M.fromList $ zip [1..] (replicate n IS.empty)
  putStrLn $ unwords $ map show $ solve m mp abs

-- solve :: Int -> M.Map Int IS.IntSet -> [(Int,Int)] -> [Int]
solve m mp [] = []
solve m mp ((a,b):abs)
  | IS.size s2 == m = a : solve m mp2 abs
  | otherwise = solve m mp2 abs
  where
    s = mp M.! a
    s2 = IS.insert b s
    mp2 = M.insert a (trace (show s2) s2) mp

提出

https://atcoder.jp/contests/abc424/submissions/69477255

C問題

最初dfsで解けずUnionFindに変更しだめでbfsでも解けず。。。
コンテスト後に間違いに気づきdfsとbfsでなんとか解けました。

提出(BFS)

事前に作成してあるBFSのテンプレートでは節点nに到達したら終了という条件にしていてこの部分の修正漏れ。

https://atcoder.jp/contests/abc424/submissions/69509050

提出(DFS)

経路上の節点数を全て集めて個数を返してしまっていた。重複点を除去するか別途保持している通過した点の数を数えればよかった。
https://atcoder.jp/contests/abc424/submissions/69509590

おわりに

Dはざっと問題読んでも効率的な実装が思いつかなかったのもありCで粘って撃沈。