AtCoder Rated参加です
結果
今回もABの2完でした。
ふりかえり
A問題
- 問題
- 回答
12で剰余を取ります。剰余が0の時は12にしましょう。
main :: IO ()
main = do
[x, y] <- getInts
let ans = (x + y) `mod` 12
print $ bool ans 12 (ans == 0)
B問題
- 問題
- 回答
問題の制約等から、transposeしてその回の投票ごとにスコアを計算していけばいいことがわかります。
その回の投票がすべて同じ場合はみんな加算されるので考慮しなくて良いのですが、一応問題の通りに実装しました。
その回の投票で、少数派だった人全員にスコアを付与するのですが、その実装方法を検討するのに時間がかかってしまいました。
結局、投票回ごとに+1するユーザをすべて(人, 1)の形で持っておき、最後にaccumArrayで足し合わせる形にしました。
main :: IO ()
main = do
[n, m] <- getInts
ss <- transpose <$> replicateM n getLine
let ws =
[ if o == 0
then '0'
else
if z == 0
then '1'
else bool '1' '0' (o > z)
| s <- ss,
let o = countBy (== '1') s,
let z = n - o
]
zs = zip ws $ map (zip [1 ..]) ss
vs =
foldl'
( \acc (v, lst) ->
acc ++ [(ii, 1) | (ii, vv) <- lst, vv == v]
)
[]
zs
ans = accumArray (+) 0 (1, n) vs :: UArray Int Int
max = snd $ maximumBy (compare `on` snd) $ assocs ans
printList $ sort $ findArrayIndices (== max) ans
C問題 (upsolved)
- 問題
- 回答
時間が足りずにupsolvedになりました。
方針としては、毎回すべてminを計算すると時間が足りないので、最初にスコアを持っておきます。そして、変更する値のところだけ差分を計算するようにします。
クエリの度に値を更新するので、現在のminのMArray, aのMArray, bのMArrayを持っておきます。
main :: IO ()
main = do
[n, q] <- getInts
as <- getInts
bs <- getInts
qs <- replicateM q do
[c, x, v] <- words <$> getLine
return (head c, read @Int x, read @Int v)
let init = zipWith min as bs
sc = sum init
arr <- newListArray (1, n) init :: IO (IOUArray Int Int)
aArr <- newListArray (1, n) as :: IO (IOUArray Int Int)
bArr <- newListArray (1, n) bs :: IO (IOUArray Int Int)
foldForM_ sc qs $ \acc (c, x, v) -> do
qCurr <-
if c == 'A'
then readArray bArr x
else readArray aArr x
let m = min v qCurr
curr <- readArray arr x
let acc' = acc - curr + m
when (c == 'A') $ updateArray aArr x (const v)
when (c == 'B') $ updateArray bArr x (const v)
updateArray arr x (const m)
print acc'
return acc'
全体を振り返って
速解きできないとレート上がらなさそう…
とりあえずB, Cの問題を速く解けるようにしないとかなあ