ABC372の振り返りです。今回早めに振り返りです
結果
A,Bの2完でした。Bでハマってしまった..
解説
A問題
- 問題
- 回答
filterします
main :: IO ()
main = do
s <- getLine
putStrLn $ filter (/= '.') s
B問題
- 問題
- 回答
解き方わからなさすぎてハマってしまいました。
大きい数からパターンマッチして引いていくことで解くことができました。
main :: IO ()
main = do
m <- readLn @Int
let ans = solve m (0, [])
print $ fst ans
putStrLn $ unwords $ map show $ snd ans
solve :: Int -> (Int, [Int]) -> (Int, [Int])
solve n (len, lst)
| n >= 3 ^ 10 = solve (n - 3 ^ 10) (len + 1, 10 : lst)
| n >= 3 ^ 9 = solve (n - 3 ^ 9) (len + 1, 9 : lst)
| n >= 3 ^ 8 = solve (n - 3 ^ 8) (len + 1, 8 : lst)
| n >= 3 ^ 7 = solve (n - 3 ^ 7) (len + 1, 7 : lst)
| n >= 3 ^ 6 = solve (n - 3 ^ 6) (len + 1, 6 : lst)
| n >= 3 ^ 5 = solve (n - 3 ^ 5) (len + 1, 5 : lst)
| n >= 3 ^ 4 = solve (n - 3 ^ 4) (len + 1, 4 : lst)
| n >= 3 ^ 3 = solve (n - 3 ^ 3) (len + 1, 3 : lst)
| n >= 3 ^ 2 = solve (n - 3 ^ 2) (len + 1, 2 : lst)
| n >= 3 = solve (n - 3 ^ 1) (len + 1, 1 : lst)
| n >= 1 = solve (n - 1) (len + 1, 0 : lst)
| n == 0 = (len, lst)
| otherwise = error "invalid pattern"
ちなみに、再帰を使うとこう書けます（こちらを参考にしました）
main :: IO ()
main = do
m <- readLn @Int
let ans = solve m [] 10
print $ length ans
putStrLn $ unwords $ map show ans
solve :: Int -> [Int] -> Int -> [Int]
solve m arr n
| n < 0 = arr
| m >= 3 ^ n = solve (m - 3 ^ n) (n : arr) n
| otherwise = solve m arr (n - 1)
C問題(upsolved)
- 問題
- 回答
普通に書くとTLEになるので工夫が必要です。
文字列を状態として持っておいて、更新するたびに更新箇所近傍を調査します。
更新するindexが3文字の最初、真ん中、最後の3パターンがあるので、このindexをxとして
[x - 2 .. x + 2]
の部分文字列を更新前後で切り出し、"ABC"が含まれる数をカウントして差を取ることで、求める差分を計算することができます。
これをコードとして書くとこのようになります。
main :: IO ()
main = do
[n, q] <- getInts
s <- getLine
xcs <- replicateM q do
[x, c] <- words <$> getLine
return (read @Int x, c)
-- 文字列をIOArrayとしてもっておく
sa <- newArray_ (-1, n + 2) :: IO (IOArray Int Char)
forM_ [-1, 0, n + 1, n + 2] (\i -> writeArray sa i '.')
mapM_ (uncurry (writeArray sa)) $ zip [1 .. n] s
let m0 = countSubstring "ABC" s
foldM_
( \m (x, c) -> do
d1 <- checkABC sa x
writeArray sa x (head c)
d2 <- checkABC sa x
let m1 = m + (d2 - d1)
print m1
return m1
)
m0
xcs
checkABC :: IOArray Int Char -> Int -> IO Int
checkABC sa x = do
cs <- mapM (readArray sa) [x - 2 .. x + 2]
return $ countSubstring "ABC" cs
この回答は↓を参考にしました。
https://atcoder.jp/contests/abc372/submissions/58001062
全体を振り返って
Bではまってしまった。ぼちぼちがんばります！
おまけ
Rustの回答
window関数べんりですね