AtCoder Beginner Contest 328 振り返り

flower

2023年11月12日 00:13

今週も振り返り。

結果

C問題がTLEで解けずに、今回はA, Bの2完でした。

レートはほぼ変わらずです。

各問題の振り返り

A,Bは解けましたが、CがTLEになってしまいました。

A - Not Too Hard

リストからある値以下の値を抜き出して合計する問題。
問題名の通り、それほど難しくはなかったです。filterして合計値を算出することで算出できました。

main :: IO ()
main = do
  [_, x] <- readInputIntList
  ss <- readInputIntList

  print $ sum $ filter (<= x) ss

B - 11/11

各月の月と日付のうち、ゾロ目になっている個数を算出する問題です。月と日数は標準入力で与えられます。
各月ごとの日数の配列を作っておいて、文字列にして全ての文字が同じであることを判定する(all (head list) list)と解けます。リスト内包表記が便利なのですが、いまいち使い慣れておらず時間がかかってしまいました。

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

  print $ countZoromeDays ss

isZorome :: Int -> Int -> Bool
isZorome m d = all (== head str) str
  where
    str = show m ++ show d

countZoromeDays :: [Int] -> Int
countZoromeDays daysPerMonth = sum [1 | m <- [1 .. length daysPerMonth], d <- [1 .. daysPerMonth !! (m - 1)], isZorome m d]

C - Consecutive

問題: https://atcoder.jp/contests/abc328/tasks/abc328_c
回答(TLE): https://atcoder.jp/contests/abc328/submissions/47497284
- upsolved: https://atcoder.jp/contests/abc328/submissions/47508409

ある範囲の文字列から、隣り合う文字が重複している個数を算出する問題です。最初はあらかじめ計算して重複する文字列のインデックスをリストに持っておけば解けると思っていたのですが、このやり方だと毎回重複する文字数を計算することになるので、TLEになってしまいます。(計算量はO(n^2)になるはず。)

main :: IO ()
main = do
  [_, q] <- readInputIntList
  ss <- getLine
  lrs <- replicateM q readPairInt

  let adjacentIdxs = findAdjacentChars ss

  mapM_ (\(l, r) -> print (length (filter (\idx -> idx >= l && idx < r) adjacentIdxs))) lrs

findAdjacentChars :: String -> [Int]
findAdjacentChars [] = []
findAdjacentChars [_] = []
findAdjacentChars xs = [i | (i, (a, b)) <- zip [1 ..] (zip xs (tail xs)), a == b]

結果を見ると、今回の実行時間は2213 msでした。

で、計算量を抑えるためにどうすればいいかというと、scanl(https://hoogle.haskell.org/?hoogle=scanl)で計算途中の値をリストに残して置けるのでこれを使います。書き直したコードはこんな感じです。qsの各要素に対してlengthをしていたのがなくなったので、計算量もO(n)になっているはずです。

main :: IO ()
main = do
  [_, q] <- readInputIntList
  ss <- V.fromList <$> getLine
  qs <- V.fromList <$> replicateM q readPairInt

  let counts = V.scanl' (\acc (a, b) -> if a == b then acc + 1 else acc) 0 $ V.zip ss (V.tail ss)

  mapM_ (print . \(l, r) -> counts V.! (r - 1) - counts V.! (l - 1)) qs

これをすると、以下のコードで重複した個数を算出することができます。

counts V.! (r - 1) - counts V.! (l - 1)

実行時間が343msまで短縮できました。

全体を振り返って

解けない問題ではなかったのですが、scanlを使う発想が浮かばずにTLEになってしまいました。前にもこう言うことあったのにな。。
場数が足りていない気がしているので、もっと過去のdailyコンテストとか使って解く問題数を増やしていこうと思います。
別件ですが、今回からcopilotを切って参加してみました。copilotをつけているとどうしても頼ってしまって解法が身に付きづらいのと、思考がcopilotに分断される感覚があったためです。
copilotが無くなったことで定型的な処理を書くのは面倒になりますが、こちらの方が自分が競プロやるにはいい気がします。もっと自分の頭を使ったほうが速い気がする。
もっと強いプログラマになりたいなーー

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