HaskellでABC471を解く

はじめに

2週間ぶりの参加です。今回は問題が優しめだったようでD問題まで解けましたが順位はあまり変動せずでした。

A問題

割り算がポイントで adivb == 9 とすると間違いになります。コンテスト中は b*9 == a に直して判定しましたが分数としてそのまま扱うという作戦もありますね。

A問題提出

main = do
  [a',b'] <- readInts
  let a = a' % 1
  let b = b' % 1
  let ans1 = any (==9) [a+b,a-b,a*b,a/b]
  putStrLn $ if ans1 then "Nine" else "Nein"

B問題

いったん大文字にした後出現回数の最大値を出力します。

B問題提出

main = do
  n <- readLn :: IO Int
  ss <- fmap sort <$> replicateM n $ do
    fmap toUpper <$> getLine
  let ans = maximum $ map length $ group ss
  print ans

C問題

これは問題文通りに問いていきます。Setを使って現在地点により近いものを順番に取り出していきます。

C問題提出

main = do
  n <- readLn :: IO Int
  as <- readInts
  let s = IS.fromList as
  print $ solve s

solve = step 0 0
  where
    step pos total s
      | isNothing cand1 && isNothing cand2 = total
      | isJust cand1 && isNothing cand2 = step pos1 (total + len1) (IS.delete pos1 s)
      | isNothing cand1 && isJust cand2 = step pos2 (total + len2) (IS.delete pos2 s)
      | len1 <= len2 = step pos1 (total+len1) (IS.delete pos1 s)
      | otherwise = step pos2 (total+len2) (IS.delete pos2 s)
      where
        cand1 = IS.lookupLT pos s
        cand2 = IS.lookupGT pos s
        pos1 = fromJust cand1
        pos2 = fromJust cand2
        len1 = abs (pos - pos1)
        len2 = abs (pos - pos2)

D問題

Query1時点で0[s]からの時間でデータを保持しておけばQuery2の時点での時間は一番大きいものから取り出せば良いことにできます。私はSetを使いましたがHeapを使った方がこの問題には合ってそうです。

D問題提出

main = do
  [n,vmax] <- readInts
  qs <- replicateM n $ do
    query <- readInts
    return  ( case query of
                (1:t:w:_) -> Q1 t w
                (2:t:_) -> Q2 t
                _ -> error "error"
            )

  putStr $ unlines $ map show $ solve vmax qs

solve v = step emptyMM
  where
    step mm [] = []
    step mm ((Q1 t w):qs) = step (insertMM (w-t) 1　mm) qs
    step mm ((Q2 t):qs) = val : step delMM qs
      where
        key = case MM.lookupMax mm of
                Nothing -> (-1)
                Just (k,_) -> k
        val = if key == -1 then -1 else min (key+t) v
        delMM = if key == -1 then mm else deleteMM key 1 mm

おわりに

せっかくD問題まで解けたのですがあまり順位上がらずちょっと残念でした。