最近参加できていないですが、ABC413参加したので振り返りです。
今回は1時間遅れのUnratedでした。
結果
今回はABの2完でした。
Unratedなので順位の変動はなしです。
ふりかえり
A問題
- 問題
- 回答
配列の合計がm以下であることを判定すれば良いです。
main :: IO ()
main = do
[_, m] <- getInts
as <- getInts
printYn $ sum as <= m
B問題
- 問題
- 回答
リスト内包表記を使って全ての組み合わせを抽出し、nubOrdで重複を排除してカウントしました。
main :: IO ()
main = do
n <- readLn @Int
ss <- replicateM n getLine
print $ (length . nubOrd) [(ss !! i) ++ (ss !! j) | let idx = [0 .. n - 1], i <- idx, j <- idx, i /= j]
C問題
- 問題
- 回答
Data.Sequenceをキューとして使い、クエリ毎に処理していくことで解きます。
ただ、pushする時の繰り返しの数cの範囲が1≤c≤10^9, popする時の個数kが1≤k≤min(10^9 ,n)となっているため、律儀にpushやpopをするとTLEになってしまいます。
そのため、ある値とその繰り返しの数を(繰り返しの数, 値)のようなタプルにしてpushするようにします。
このような方法はランレングス圧縮1と呼ばれています。
本番ではランレングス圧縮が必要なことに気づかずTLEで終わってしまいました。
main :: IO ()
main = do
q <- readLn @Int
qs <- replicateM q getInts
let seq = Seq.empty
foldM_
( \seq q -> case q of
[1, c, x] -> return $ seq :|> (c, x)
[2, k] -> do
let (remaining, total) = removeK k seq 0
print total
return remaining
_ -> error "invalid query pattern"
)
seq
qs
removeK 0 seq acc = (seq, acc)
removeK k seq acc =
case seq of
Seq.Empty -> (seq, acc)
(count, val) :<| rest
| k >= count -> removeK (k - count) rest (acc + count * val)
| otherwise -> ((count - k, val) :<| rest, acc + k * val)
全体を振り返って
最近忙しくて中々参加できないのですが、そろそろ復帰したいです。