AtCoder Beginner Contest 329 振り返り

flower

遅くなりましたが振り返ります。

結果

C問題まで溶けましたが、DがTLEでした。

レートはちょっとだけ上がりました。

各問題の振り返り

今回あまり難しくなかったなあと思っていたのですが、Dまで灰色でした。Dも解きたかったなあ。

A - Spread

文字列に空白を挟む問題。文字列をリストに変換してunwordsすれば解けます。

main :: IO ()
main = do
  ss <- getLine :: IO String
  putStrLn $ unwords $ map (: []) ss

B - Next

最大の数以外で最大の数を求めるという問題。ユニークにして降順ソートして2番目の値を取り出せば解けます。

main :: IO ()
main = do
  _ <- readInputInt
  as <- readInputIntList
  print $ L.sortOn Down (L.nub as) !! 1

C - Count xxx

空でない一文字からなる部分文字列を取り出して、その数をカウントする問題。まずは文字列をgroupで一文字からなる文字列に分割し（便利！）、部分文字列の文字数をHashに追加していきます。この時に、文字数が既に登録されている文字列の文字数より大きい時だけ追加するようにするのがポイントでした。今考えると、IntMapでもよかったかも。あとUArrayでもいけるらしい。（別の機会にやります）

main :: IO ()
main = do
  _ <- readInputInt
  ss <- L.group <$> getLine

  print $ solve ss

solve :: [[Char]] -> Int
solve ss = HS.foldl' (+) 0 $ go ss
  where
    countLen h s = case HS.lookup ch h of
      Just v -> if lenS > v then HS.insert ch lenS h else h
      Nothing -> HS.insert ch lenS h
      where
        ch = head s
        lenS = length s
    go = L.foldl' countLen HS.empty

D - Election Quick Report

選挙の投票数をカウントする問題で、1票ごとに現在の投票の最大投票数をカウントする問題です。
会えなくTLEで終わってしまいましたが、そんなに難しい問題ではなかったと思います。

TLEになった回答はこちらです。

main :: IO ()
main = do
  _ <- readInputInt
  as <- V.fromList <$> readInputIntList

  let result = V.scanl' (\h a -> HS.insertWith (+) a 1 h) HS.empty as
  mapM_ solve result

solve :: HS.HashMap Int Int -> IO ()
solve h = Data.Foldable.forM_ (findMaxValueMinKey h) print

findMaxValueMinKey :: HS.HashMap Int Int -> Maybe Int
findMaxValueMinKey = snd <$> HS.foldlWithKey' update (Nothing, Nothing)
  where
    update result@(maxValue, minKey) key value
      | Just v <- maxValue, v > value = result
      | Just v <- maxValue, v == value = (maxValue, Just $ maybe key (min key) minKey)
      | otherwise = (Just value, Just key)

実行時間は2212msでした。

この回答の何が不味かったかというと、まずここで標準入力したリスト(as)に対してscanl'して

let result = V.scanl' (\h a -> HS.insertWith (+) a 1 h) HS.empty as

ここで、scanl'の結果に対してmapM_しています。

mapM_ solve result

で、solveの中でData.HashMap.StrictのfoldlWithKey'関数を使っています。

findMaxValueMinKey :: HS.HashMap Int Int -> Maybe Int
findMaxValueMinKey = snd <$> HS.foldlWithKey' update (Nothing, Nothing)
  where
    update result@(maxValue, minKey) key value
      | Just v <- maxValue, v > value = result
      | Just v <- maxValue, v == value = (maxValue, Just $ maybe key (min key) minKey)
      | otherwise = (Just value, Just key)

この関数の計算量はO(n)なので、全部でO(n^3)の計算量になってしまうので、計算時間オーバーでTLEになってしまいます。そりゃそうだよね。
(参考: https://hackage.haskell.org/package/unordered-containers-0.2.19.1/docs/Data-HashMap-Strict.html)

対処法としては、投票を終えてからループして最小投票数を探すのではなく、投票するたびに最大投票数を更新してそれを返り値にし、リストにすると言うものです。また、"最も得票数が多かった候補者が複数いる場合は、その中で最も番号の小さい候補者が当選となります。"との制約があることから、最大投票数を検索するときは投票数をマイナスに反転させて投票番号とタプルにし、minで抽出しています。（こうすると、最大投票数が同じ時に投票番号が小さい方が小さいと判断されます。）
実装しなおすと以下のようになります。（実装はhttps://atcoder.jp/contests/abc329/submissions/47741809を参考にさせていただきました。

main :: IO ()
main = do
  _ <- readInputInt
  as <- readInputIntList

  let cands = step IM.empty (0, -1) as
  putStr $ unlines $ map show cands

step :: IM.IntMap Int -> (Int, Int) -> [Int] -> [Int]
step im mn [] = []
step im mn (a : as) = ans : step im1 mn1 as
  where
    im1 = IM.insertWith (+) a 1 im
    cnt = im1 IM.! a
    mn1 = min mn (-cnt, a)
    ans = snd mn1

これで提出し直すと、実行時間が262msになりました。Vectorなどを使うともっと高速化するかもしれません。

全体を振り返って

D問題まで解けない問題ではなかったのですが、C問題を解いたところでちょっと満足してしまったのが失敗だったかなと思っています。
また、 D問題自体も愚直に解いてしまって、リストの走査を増やしてしまったのが失敗でした。途中経過を算出する問題は計算が終わった後に計算しなおさなくても、1回の走査で途中経過を記録しておけば計算量を減らせるので、次回以降はここを意識していきたいと思っています。

おまけ

鉄則本を買ってしまったので、今日から少しづつ解いていきたいと思います。いつも思うのですが、技術書に限って物欲が弱い。。
https://book.mynavi.jp/ec/products/detail/id=131288

この記事が気に入ったらサポートをしてみませんか？