AtCoder477振り返りです。
最近ずっとさぼってたので久しぶりの出場です
結果
AB2完でした。大怪我です
ふりかえり
A問題
- 問題
- 回答
問題文通りにときました。
main :: IO ()
main = do
c <- getLine
putStrLn $ case c of
"B" -> "Y"
"Y" -> "R"
"R" -> "B"
_ -> error "invalid char: " <> c
B問題
- 問題
- 回答
zipWith3を使って前後の差を計算します。
端が漏れるので、そこは別途計算してリストに結合します。
main :: IO ()
main = do
[n, d] <- getInts
xs <- sortOn snd . zip [1 ..] <$> getInts
let z3 = zipWith3 (\(_, a) (i, b) (_, c) -> if b - a >= d && c - b >= d then (i, True) else (i, False)) xs (drop 1 xs) (drop 2 xs)
xv = V.fromList xs
h = (fst (xv V.! 0), snd (xv V.! 1) - snd (xv V.! 0) >= d)
t = (fst (xv V.! (n - 1)), snd (xv V.! (n - 1)) - snd (xv V.! (n - 2)) >= d)
res = [i | (i, b) <- (h : z3) <> [t], b]
size = length res
print size
printList $ sort res
C問題
- 問題
- 回答(upsolved)
クエリごとに部分文字列が含まれるかどうかを計算するとTLEすることは明らかです。そのため計算量を削減する方法を考えます。
事前に部分文字列の含まれる場所を計算して、その開始位置を計算しておくとよさそうです。
そのあとのクエリ処理が問題ですが、ここは累積和を使って出現回数を計算しておき、区間内の値が1以上であることを計算しておけばよいです。（今回はここに気づかずTLEとなりました。）
回答コードは以下の通りです
-- >>> solve "abcdabc" "bc" [(2,6), (3,5), (3,7)]
-- [True,False,True]
solve :: String -> String -> [(Int, Int)] -> [Bool]
solve s t = map q
where
q (l, r)
| r - l + 1 < lenT = False
| otherwise = (arr IA.! (r - (lenT - 1)) - arr IA.! (l - 1)) > 0
lenS = length s
lenT = length t
arr = g lenS t (f lenT s)
-- >>> f 2 "abcdabc"
-- ["ab","bc","cd","da","ab","bc","c"]
f :: Int -> String -> [String]
f l xs = go xs
where
go xs
| null sb = []
| otherwise = sb : go (drop 1 xs)
where
sb = take l xs
-- >>> g 7 "bc" ["ab","bc","cd","da","ab","bc", "c"]
-- array (0,7) [(0,0),(1,0),(2,1),(3,1),(4,1),(5,1),(6,2),(7,2)]
g :: Int -> String -> [String] -> UArray Int Int
g n t tl = IA.array (0, n) $ zip [0 ..] $ scanl' (+) 0 [bool 0 1 (t == tt) | tt <- tl]
-- Main
main :: IO ()
main = do
q <- getInt
s <- getLine
t <- getLine
qs <- replicateM q getPairInt
mapM_ printYn $ solve s t qs
全体を振り返って
久しぶりに出たのですが、やはり頻度を上げた方がいいなーと感じました。
レートが下がるリスクはありますが、さぼらずRatedで参加するようにしたいと思います