HaskellでABC466を解く

はじめに

C問題でO(N^2)のアルゴリズムをO(2N)のアルゴリズムに変換できず。D問題は逆方向からやればO(M)でできることに気づいて間に合いました。

A問題

全部がマイナスだったら Yes それ以外は No と回答します。

A問題提出

main = do
  _n <- readLn :: IO Int
  xs <- readInts
  putStrLn $ bool "No" "Yes" $ all (<0) xs

B問題

Mapを作るときにmaxを使うと最大のものを保存できます。

B問題提出

main = do
  [n,m] <- readInts
  css <- replicateM n $ do
    [c,s] <- readInts
    return (c,s)
  let mp = M.fromListWith max css
  let ans = [ M.findWithDefault (-1) i mp | i <- [1..m]]
  putStrLn $ unwords $ map show ans

C問題

O(N^2)のアルゴリズムで提出してREになりました。その後二分探索すればよいかと思いましたがそれでもO(N*logN)で間に合いません。ここで諦めました。コンテスト後にO(2N)ってことは尺取り法で行けるんだと言うことで納得しました。

C問題提出

main = do
    hSetBuffering stdout NoBuffering
    n <- readLn
    solve n

solve n = step 1 2 0
  where
    step :: Int -> Int -> Int -> IO ()
    step i j ans
        | i >= n = do
            putStrLn $ "! " ++ show ans
        | j > n = do -- i から n まで全部距離1以下
            step (i+1) (max (i+2) j) (ans + (n-i))
        | otherwise = do
            putStrLn $ "? " ++ show i ++ " " ++ show j
            hFlush stdout
            res <- getLine
            case res of
                "Yes" -> step i (j+1) ans
                "No" -> step (i+1) (max j (i+2)) (ans + (j-i-1))
                _ -> return ()

D問題

後ろから作ると上手く行きますね。

D問題提出

main = do
  [n,m] <- readInts
  rcs <- fmap reverse <$> replicateM m $ do
    [r,c] <- readInts
    return (r,c)
  let (_,_,ans) = solve rcs
  print ans

solve = step IS.empty IS.empty 0
  where
    step rows cols cnt [] = (rows,cols,cnt)
    step rows cols cnt ((r,c):rcs)
      | IS.notMember r rows && IS.notMember c cols = step (IS.insert r rows) (IS.insert c cols) (succ cnt) rcs
      | IS.notMember r rows = step (IS.insert r rows) cols cnt rcs
      | IS.notMember c cols = step rows (IS.insert c cols) cnt rcs
      | otherwise = step rows cols cnt rcs

おわりに

今回はC問題を一旦諦めてD問題に行ってギリギリキープという感じで終わりました。