AtCoder Beginner Contest 331 振り返り
早速振り返りです!
結果
今回Bで沼りまくって2完で終わってしまいました…
なんとか2完できてよかった
![](https://assets.st-note.com/img/1701537521502-BTUoKvNuZ9.png?width=1200)
![](https://assets.st-note.com/img/1701537486250-GL43ufAlXS.png?width=1200)
各問題の振り返り
A - Tomorrow
問題見て一瞬ビビったのですが、特に難しい問題ではないです。
日付と月の最大値を意識すれば普通に解けます。
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
あれ?これ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
回答(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)がいい感じなので、いい感じに取り組みながらレベルアップしていきたいなー。停滞気味なので早く脱したい
この記事が気に入ったらサポートをしてみませんか?