AtCoder Beginner Contest 331 振り返り

早速振り返りです！

結果

今回Bで沼りまくって2完で終わってしまいました…
なんとか2完できてよかった

各問題の振り返り

A - Tomorrow

• 問題: https://atcoder.jp/contests/abc331/tasks/abc331_a

• 回答: https://atcoder.jp/contests/abc331/submissions/48109090

問題見て一瞬ビビったのですが、特に難しい問題ではないです。
日付と月の最大値を意識すれば普通に解けます。

main :: IO ()
main = do
  [ml, dl] <- readInputIntList
  [y, m, d] <- readInputIntList

  putStrLn $ unwords $ map show $ addDate (ml, dl) (y, m, d)

addDate :: (Int, Int) -> (Int, Int, Int) -> [Int]
addDate (ml, dl) (y, m, d)
  | d < dl = [y, m, d + 1]
  | m < ml = [y, m + 1, 1]
  | otherwise = [y + 1, 1, 1]

B - Buy One Carton of Milk

• 問題: https://atcoder.jp/contests/abc331/tasks/abc331_b

• 回答: https://atcoder.jp/contests/abc331/submissions/48143976

あれ？これDP？と勘違いして沼ってしまった問題。DP全然慣れていなかったのと、B問題でDPが出ると思ってなかったのでビビってしまいました。
購入したい卵の個数がパックの卵の個数より少ない場合も考慮する必要があったので、その辺りも頭を悩ませた要因です。
回答はこのような感じになります。なんとか時間ギリギリにAC出せて安心しました。

main :: IO ()
main = do
  [n, s, m, l] <- readInputIntList

  let v = minCost s m l n
  let res = comp v n s m l
  print res

comp v n s m l
  | n < 6 = minimum [s, m, l]
  | n >= 6 && n < 8 = minimum [v, m, l]
  | n >= 8 && n < 12 = min v l
  | otherwise = v

minCost :: Int -> Int -> Int -> Int -> Int
minCost s m l n = dp A.! n
  where
    minPackCost = minimum [s, m, l]
    dp = A.listArray (0, n) $ 0 : [minValue i | i <- [1 .. n]]

    minValue i =
      minimum $
        filter
          (> 0)
          [ if i < 6 then minPackCost else maxBound,
            if i >= 6 then dp A.! (i - 6) + s else maxBound,
            if i >= 8 then dp A.! (i - 8) + m else maxBound,
            if i >= 12 then dp A.! (i - 12) + l else maxBound
          ]

後で知ったのですが、制約条件$${1≤N≤100}$$からDPを使う必要はなく、全探索でも十分解けることがわかりました。その場合はこのような解法になります。前も言いましたが、全探索ではリスト内包表記が便利ですね。

main :: IO ()
main = do
  [n, s, m, l] <- readInputIntList

  print $ minCost s m l n

minCost :: Integral a => a -> a -> a -> a -> a
minCost s m l n = minimum [s * i + m * j + l * k | i <- [0 .. limit], j <- [0 .. limit], k <- [0 .. limit], 6 * i + 8 * j + 12 * k >= n]
  where
    limit = (n `div` 6) + 1

全探索の回答はhttps://atcoder.jp/contests/abc331/submissions/48147159においています。

C - Sum of Numbers Greater Than Me

• 問題: https://atcoder.jp/contests/abc331/tasks/abc331_c

• 回答(upsolved): https://atcoder.jp/contests/abc331/submissions/48153194

二分探索と累積和の合わせ技で解く問題です。あらかじめsortして累積和で解いておいて、二分探索でindexを探して計算します。
ListとArray.Unboxedの使い分けがちょっと面倒でした。

main :: IO ()
main = do
  n <- readLn @Int
  as <- readInputIntList

  let sortedList = L.sort as
  let sortedArr = AU.listArray (1, length sortedList) sortedList
  let cumulativeSum = AU.listArray (1, length sortedArr + 1) $ L.scanl' (+) 0 sortedList

  putStrLn $ unwords $ map show $ solve cumulativeSum sortedArr as

solve :: AU.Array Int Int -> AU.Array Int Int -> [Int] -> [Int]
solve cumulativeSum sortedArr arr =
  let totalSum = cumulativeSum AU.! snd (AU.bounds cumulativeSum)
      getSum i = totalSum - (cumulativeSum AU.! i)
   in L.map (\x -> getSum (binarySearch sortedArr x 1 (length sortedArr))) arr

binarySearch :: (Ord t2, AU.Ix t1, Integral t1) => AU.Array t1 t2 -> t2 -> t1 -> t1 -> t1
binarySearch arr val low high
  | high < low = low
  | otherwise =
      let mid = low + (high - low) `div` 2
       in if arr AU.! mid <= val
            then binarySearch arr val (mid + 1) high
            else binarySearch arr val low (mid - 1)

全体を振り返って

B問題は制約条件を見て焦らず解くべきでした。反省。
今回までにプロパティベーステスト使えるようにしたかったのですが、今週時間が取れなかったのと想像以上に奥が深かったので今回使えるレベルに至りませんでした。次回までに少しは使えるようにしたい。

鉄則本(https://book.mynavi.jp/ec/products/detail/id=131288)がいい感じなので、いい感じに取り組みながらレベルアップしていきたいなー。停滞気味なので早く脱したい