HaskellでABC476を解く

はじめに

今週はCまででした。

A問題

最後の文字が'e'かどうか調べて出力する文字列を変化させます。

A問題提出

main = do
  s <- getLine
  putStrLn $ s ++ if last s == 'e'
                  then "r"
                  else "er"

B問題

SとTの文字列の文字が同じ場合、またはTの文字が'*'の場合はOKとして
全体がOKの状態かを判定します。

B問題提出

main = do
  _n <- readLn :: IO Int
  s <- getLine
  t <- getLine
  let st = zipWith (\x y -> x == y || y == '*') s t
  putStrLn $ bool "No" "Yes" $ and st

C問題

必要な最初の大きい3つだけをHeapで管理すればよいです。管理している数の最小値よりも大きい値がきたら入れ替えるという処理を続けます。

C問題提出

main = do
  n <- readLn :: IO Int
  (a1:a2:a3:as) <- readInts
  let ans = solve (H.fromList [a1,a2,a3]) as
  putStr $ unlines $ map show ans

solve = step
  where
    step h [] = [H.minimum h]
    step h (a:as) = H.minimum h : step h1 as
      where
        h1 = if a > H.minimum h
             then H.insert a (H.deleteMin h)
             else h

D問題

コンテスト中はBからできるだけ買って、お釣りを含めた残額でAから買い物すれば良いと考えてテストケースは通りましたがWAとなりました。公式回答を読んで解き直したのが以下です。Bで何個買えるかを調べてBの買えるものとAをソートして残額で買えるだけ買っていくということをすると２分探索も必要なく解けます。

D問題提出

main = do
  [n,m,k] <- readInts
  [x,y] <- readInts
  as <- readInts
  bs <- sort <$> readInts
  let bs' = drinksInBudget k y bs
  let as' = sort $ as ++ bs'
  print $ length $ foodAndDrinkInBudget (k*y+x) as'

foodAndDrinkInBudget budget = step 0
  where
    step moneyUsed [] = []
    step moneyUsed (a:as)
      | moneyUsed1 <= budget = a : step moneyUsed1 as
      | otherwise = []
      where
        moneyUsed1 = moneyUsed + a

drinksInBudget k y = step 0
  where
    step _yUsed [] = []
    step yUsed (b:bs)
      | yUsed1 <= y = b : step yUsed1 bs
      | otherwise = []
      where
        yUsed1 = yUsed + (b+k-1)`div`k

E問題

SegTreeの問題でした。コンテスト中は解けませんでしたが用意していたSegTreeのライブラリですんなり解けました。

E問題提出

main = do
  [n,m] <- readInts
  ps <- map (subtract 1) <$> readInts -- 0-indexed
  qs <- replicateM m $ do
     [l,r] <- readInts
     return (l-1,r) -- 0-indexed
  let cands = solve ps qs
  let ans = map snd $ sort $ zip (VU.toList cands) [0..]
  putStrLn $ unwords $ map (show.(+1)) ans

solve :: [Int] -> [(Int,Int)] -> VU.Vector Int
solve ps qs = runST $ do
  let vMin = V.fromList $ map Min ps -- Monoid aの初期Vectorを作成
  let vMax = V.fromList $ map Max ps -- Monoid aの初期Vectorを作成
  stMin <- buildSegTree vMin
  stMax <- buildSegTree vMax
  vPos <- VU.thaw $ VU.fromList $ map snd $ sort $ zip ps [0..]
  -- step stMin stMax vPos qs
  step stMin stMax vPos qs
  VU.freeze vPos
  where
    step _stMin _stMax _vPos [] = return ()
    step stMin stMax vPos ((x,y):qs) = do
      vMin <- prodSegTree stMin x y -- 0-indexed, [l,r)
      vMax <- prodSegTree stMax x y -- 0-indexed, [l,r)
      let minVal = getMin vMin
      let maxVal = getMax vMax
      iMinPos <- VUM.read vPos minVal
      iMaxPos <- VUM.read vPos maxVal
      -- swap vPos
      VUM.swap vPos minVal maxVal
      -- swap segTree
      setSegTree stMin iMaxPos vMin
      setSegTree stMin iMinPos (Min maxVal)
      setSegTree stMax iMaxPos (Max minVal)
      setSegTree stMax iMinPos vMax
      -- next step
      step stMin stMax vPos qs
      return ()

おわりに

D問題結局正しい解法になってなかった。精進します。