AtCoder Beginner Contest 372 振り返り

ABC372の振り返りです。今回早めに振り返りです

## 結果

A,Bの2完でした。Bでハマってしまった..

![スクリーンショット 2024-09-22 14.07.43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/ed1ae13e-451e-9923-753e-47db8b498d51.png)

![スクリーンショット 2024-09-22 14.08.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/03ba9f67-9c82-9a81-31e4-95dde180bb9a.png)

## 解説

### A問題

- 問題
  - https://atcoder.jp/contests/abc372/tasks/abc372_a
- 回答
  - https://atcoder.jp/contests/abc372/submissions/57954722

filterします

```haskell
main :: IO ()
main = do
  s <- getLine

  putStrLn $ filter (/= '.') s
```

### B問題

- 問題
  - https://atcoder.jp/contests/abc372/tasks/abc372_b
- 回答
  - https://atcoder.jp/contests/abc372/submissions/57988619
  - https://atcoder.jp/contests/abc372/submissions/58012736

解き方わからなさすぎてハマってしまいました。
大きい数からパターンマッチして引いていくことで解くことができました。

```haskell
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"
```

ちなみに、再帰を使うとこう書けます（[こちら](https://atcoder.jp/contests/abc372/submissions/58004141)を参考にしました）

```haskell
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)

- 問題
  - https://atcoder.jp/contests/abc372/tasks/abc372_c
- 回答
  - https://atcoder.jp/contests/abc372/submissions/58011277

普通に書くとTLEになるので工夫が必要です。
文字列を状態として持っておいて、更新するたびに更新箇所近傍を調査します。

更新するindexが3文字の最初、真ん中、最後の3パターンがあるので、このindexをxとして

`[x - 2 .. x + 2]`

の部分文字列を更新前後で切り出し、`"ABC"`が含まれる数をカウントして差を取ることで、求める差分を計算することができます。

これをコードとして書くとこのようになります。

```haskell
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関数べんりですね

- 問題C
  - https://atcoder.jp/contests/abc372/submissions/58012301