HaskellでABC479を解く

はじめに

今回はなんとかD問題まで解けました。

A問題

元々のリストのままでも間に合うかもしれませんが念の為Arrayにしてから
添字が奇数のもののみ集めました。

A問題提出

main = do
  n <- readLn :: IO Int
  as <- readInts
  let arr = AU.listArray (1,n) as :: AU.UArray Int Int
  let cands = [arr AU.! i | i <- [1..n], odd i]
  print $ sum cands

B問題

連続のものをグループにして、'R'文字のグループの中で最長のものが答えです。

B問題提出

main = do
  n <- readLn :: IO Int
  s <- getLine
  let cands = map snd $ filter ((=='R').fst) $ map (\g -> (head g, length g) ) $ group s
  if null cands then
    print 0
  else do
    print $ maximum cands

C問題

DPっぽいなと思いつつ制約が10^9までなので配列で管理する方式は使えずMapで管理します。2^10までのパターンを考えれば良いのでメモリや時間的にも問題ありません。

C問題提出

main = do
  [n,wLimit] <- readInts
  vws <- replicateM n $ do
    [v,w] <- readInts
    return (v,w)
  let ans = solve n wLimit vws
  print ans

solve n wLimit = step (IM.singleton 0 0)
  where
    step im [] = maximum $ map fst $ IM.assocs im
    step im ((val,vol):abs) = step im1 abs
      where
        post = [(v0+v1,w0+w1) | (v0,w0) <- IM.assocs im, (v1,w1) <- [(0,0), (val,vol)], w0+w1 <= wLimit ]
        im1 = IM.fromListWith min post

D問題

例えば右に行くときは素直に右に行ったときと、一旦左に行って、右に行く中で最小なものを足したものと比較して最小のものが答えになります。右に行く中で最小なものを求めるのにセグメントツリーを使いましたが公式解説ではもっと簡単に求めています。

D問題提出

main = do
  [n,q] <- readInts
  ls <- readInts
  rs <- readInts
  qs <- replicateM q $ do
    [s,t] <- readInts
    return (s-1,t) -- 0-indexed

  putStr $ unlines $ map show $ solve n (0:ls) (rs++[0]) qs

solve n ls rs qs = runST $ do
  let vecL = VU.fromList $ map Min ls -- Monoid aの初期Vectorを作成
  let vecR = VU.fromList $ map Min rs -- Monoid aの初期Vectorを作成
  stL <- buildSegTree vecL
  stR <- buildSegTree vecR
  step stL stR qs
  where
    step _stL stR [] = return []
    step stL stR ((s,t):qs)
      | s < t = do
        normal <- getSegTree stR s -- 0--indexed
        forward <- getSegTree stL s -- 0-indexed
        back <- prodSegTree stR 0 s -- 0-indexed, [l,r)
        rest <- step stL stR qs
        return (min (getMin normal) (getMin forward + getMin back) : rest)
      | otherwise = do
        normal <- getSegTree stL s -- 0--indexed
        forward <- getSegTree stR s -- 0-indexed
        back <- prodSegTree stL s n -- 0-indexed, [l,r)
        rest <- step stL stR qs
        return (min (getMin normal) (getMin forward + getMin back) : rest)

おわりに

せっかくD問題まで解けましたが遅すぎてレートはあまり変化せずでした。