HaskellでABC459を解く

はじめに

今週はC問題にハマってしまいましたがギリギリACできました。
D問題は残り10分弱で解けそうでしたが実装時間全く足りずでした。

A問題

文字列とインデクスをzipして対象のものだけ取り出し直します。

A問題提出

main = do
  x <- readLn :: IO Int
  let ans = [c | (c,i) <- zip "HelloWorld" [1..], i /= x ]
  putStrLn ans

B問題

文字と数字の辞書を作る部分途中4つの区間があったりちょっと注意する必要がありました。

B問題提出

main = do
  n <- readLn :: IO Int
  ss <- words <$> getLine
  let xs = ( concatMap (\(x,i) -> replicate x i) $ zip [3,3,3,3,3,4,3,4] [2..9] )
  let dict = M.fromList $ zip ['a'..'z'] xs
  putStrLn $ concatMap show $ solve dict ss

solve dict ss = step ss
  where
    step [] = []
    step (s:ss) = dict M.! (head s) : step ss

C問題

こういう配列を買い替えながら進めていくのは苦手です。REとかWAに悩まされましたが最終的にできました。
個数を数える配列の範囲を間違っていたのに最後気づけてよかったです。

C問題提出

main = do
  [n,q] <- readInts
  qs <- replicateM q readInts
  putStr $ unlines $ map show $ solve n q qs

solve :: Int -> Int -> [[Int]] -> [Int]
solve n q qs0 = runST $ do
  count0 <- newArray (0,3*10^5) 0 :: ST s (STUArray s Int Int) -- total counter
  writeArray count0 0 n
  block0 <- newArray (1,n) 0 :: ST s (STUArray s Int Int) -- blocks
  step 0 count0 block0 qs0
  where
    step :: Int -> STUArray s Int Int -> STUArray s Int Int -> [[Int]] -> ST s [Int]
    step lev count block [] = return []
    step lev count block ([1,x]:qs) = do
      b <- readArray block x
      let newB = succ b
      writeArray block x newB -- xの位置のBlockを1つ増やす
      c <- readArray count newB
      let newC = succ c
      writeArray count newB newC -- カウンターを1つ増やす
      if newC == n then
        step (succ lev) count block qs
      else
        step lev count block qs
    step lev count block ([2,y]:qs) = do
      if y+lev > q then do
        rest <- step lev count block qs
        return $ 0 : rest
      else do
        c <- readArray count (y+lev)
        rest <- step lev count block qs
        return $ c : rest
    step lev count arr (_:qs) = error "error"

おわりに

D問題はすぐに解法気がついたのですが残り時間足りず。C問題のようなのは相変わらず苦手です。