ABC352の振り返りです。今回はバーチャル参加です。
今回の結果
A,B,C 3完でした。
バーチャル参加なのでレーティングの変動はなしです。
各問題の振り返り
A - AtCoder Line
xとyの大小比較して[x .. y]と[y .. x]を作り、elemで存在チェックします。
main :: IO ()
main = do
[n, x, y, z] <- readInputInts
let lst = if x <= y then [x .. y] else [y .. x]
putStrLn if z `elem` lst then "Yes" else "No"
B - Typing
先頭を比較して再帰的に処理していきます。
main :: IO ()
main = do
ss <- getLine
ts <- getLine
putStrLn $ unwords . map show $ L.reverse $ solve ss ts
solve :: String -> String -> [Int]
solve ss ts = go ss ts 1 []
where
go [] _ _ res = res
go ss@(hss : tss) ts@(hts : tts) pos res =
if hss == hts
then go tss tts (pos + 1) (pos : res)
else go ss tts (pos + 1) res
C - Standing On The Shoulders
bをひとつずつ固定して他のaを全て足すという解き方だとO(N^2)となり、2≤N≤2×10^5なのでTLEになります。
なので最初に総和を取ってaとbの配列を作成しておき、各bを足してaを引く方法で解きます。これだと計算量はO(N)になります。
Haskellで気を付ける点としては、リストだと値を取得する時の計算量がO(N)となってしまうことです。
これを防ぐためにはVectorを使用します。(VectorだとO(1)で取得できる。)
実装は以下の通りです。
main :: IO ()
main = do
n <- readLn @Int
abs <- replicateM n readPairInt
let as = map fst abs
let vecAs = V.fromList as
let bs = zip [0 ..] $ map snd abs
let sumAs = L.sum as
print $ L.foldl' (\acc (i, b) -> let tmp = sumAs - (vecAs V.! i) + b in max acc tmp) 0 bs
全体を振り返って
来週もRated参加できないので、のんびりやろうと思います。
おまけ
今回もRustの回答を置いておきます。