HaskellでABC475を解く

はじめに

今回はC問題まで。C問題で時間がかかりすぎてD問題提出に間に合わずでした。

A問題

文字の途中を'o'で埋めます。コンテスト中は逐次的に処理しましたがintercalate関数がまさにそのための関数です。

A問題提出

main = do
  s <- getLine
  putStrLn $ intercalate "o" $ map (:[]) s

B問題

1000でmod取ったあとの数を1000から引くと桁ごとに必要なコイン数が分かるのでその合計を出力します。

B問題提出

main = do
  _n <- readLn :: IO Int
  as <- readInts
  let (x1,x10,x100) = solve as
  putStrLn $ show x1 ++ " " ++ show x10 ++ " " ++ show x100

solve = step (0,0,0)
  where
    step (x,y,z) [] = (x,y,z)
    step (x0,y0,z0) (a:as) = step (x0+x,y0+y,z0+z) as
      where
        (s1:s10:s100:_) = take 3 $ reverse ( show @Int (1000 - (a `mod` 1000)) ) ++ repeat '0'
        (x,y,z) = (read @Int [s1], read @Int [s10], read @Int [s100])

C問題

i個右に行って左に行けるところまで、i個左に行って右に行けるところまで数えたもののなかで最大値が答えです。行けるところまでは二分探索を使いましたのでO(NlogN)のアルゴリズムで解きました。個数の処理のところで計算が合わず想定外の時間がかかってしまいましたが無事ACできました。

C問題提出

main = do
  [n,s,l] <- readInts
  as <- readInts
  let sr = VU.fromList $ scanr (+) 0 as
  let sl = VU.fromList $ scanl (+) 0 as
  mv <- VU.thaw sl
  ans1 <- moveL mv sr s l
  ans2 <- moveR mv sl s l n
  print $ maximum $ ans1 ++ ans2

moveL mv sr s l = do
  let xs = [(i,sr VU.! i - sr VU.! (s-1)) | i <- [0..s-1]]
  forM xs $ \(i,x) -> do
    v0 <- VUM.read mv i
    ans <- VAS.binarySearchR mv (v0 + (l-x))
    return $ ans - i

moveR mv sl s l n = do
  let xs = [(i,sl VU.! i - sl VU.! (s-1)) | i <- [s-1..n-1]]
  forM xs $ \(i,x) -> do
    v0 <- VUM.read mv i
    ans <- VAS.binarySearchL mv (v0 - (l-x))
    return $ i - ans + 1

D問題

少ない残り時間のなか解き方分かって実装して提出したのですが結局1問TLEでした。結局ライブラリとして用意していた primeの計算がInteger型で処理していたのをIntにすることで間に合いました。。。

D問題提出

main = do
  s <- getLine
  let l = length s
  let cands = takeWhile (<10^l) $ dropWhile (<10^(l-1)) primes
  putStrLn $ solve s cands

solve s = step
  where
    step [] = show (-1)
    step (x:xs)
      | match s t = t
      | otherwise = step xs
      where
        t = show x

match :: String -> String -> Bool
match s t = step1 M.empty S.empty $ zip s t
  where
    step1 :: M.Map Char Char -> S.Set Char -> [(Char,Char)] -> Bool
    step1 _m _s [] = True
    step1 m s ((a,b):abs)
      | M.notMember a m && S.notMember b s = step1 (M.insert a b m) (S.insert b s) abs -- ここで一つだけ条件がある
      | M.member a m && S.member b s && m M.! a == b = step1 m s abs
      | otherwise = False

おわりに

今週はあと少しでD問題間に合わずでした。