AtCoder Beginner Contest 342 振り返り

昨日のAtCoderの振り返りです。
## 今回の結果

A,B 2完でした。CはTLEで終わりました。

![スクリーンショット 2024-02-25 13.17.04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/05379ead-dd52-6f33-6004-4d305abb5dbc.png)

![スクリーンショット 2024-02-25 13.16.31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/bf63844e-f988-acdd-f9c7-d1844938692e.png)

## 各問題の振り返り

### A - Yay!

- [問題](https://atcoder.jp/contests/abc342/tasks/abc342_a)
- [自分の回答](https://atcoder.jp/contests/abc342/submissions/50576761)

要は一文字しか出ない文字を探せば良いのですが、すんなり解けずちょっと工夫が必要でした。解法としては一文字目と残りの文字を分けて、
- 一文字目が残りの文字に現れなかったら一文字目が解
- 現れた場合はその文字が解

という風にして解きました。

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

  let (init : rest) = s

  print $ if init `notElem` rest then 1 else fromJust (L.findIndex (/= init) rest) + 2
```

### B - Which is ahead?

- [問題](https://atcoder.jp/contests/abc342/tasks/abc342_b)
- [自分の回答](https://atcoder.jp/contests/abc342/submissions/50584703)

列が与えられて、2人の人Ai, Biのうちどちらが最初の方のindexに出てくるかを求める問題です。長さNの文字列に対して、適用するクエリはQ個となります。
制約条件を見ると行列の長さNの制約条件が

```math
1≤N≤100
```

クエリの数Qが

```math
1≤Q≤100
```

となっており、文字列一つごとにクエリを実行したとしても計算量は`O(n^3)`で`1.0 * 10^6`オーダです。これ愚直に解いても行けるんじゃね…？と思ってやってみたら普通にACできました。実行時間も1msと短めです。関係ないけど`elemIndex`便利。

```haskell
main :: IO ()
main = do
  _ <- BC.getLine
  ps <- readInputInts
  q <- readLn @Int
  abs <- replicateM q readPairInt

  mapM_ (\(a, b) -> print $ if a `L.elemIndex` ps < b `L.elemIndex` ps then a else b) abs
```

### C - Divide and Divide

- [問題](https://atcoder.jp/contests/abc342/tasks/abc342_c)
- 自分の回答
  - [TLE](https://atcoder.jp/contests/abc342/submissions/50601149)
  - [upsolved](https://atcoder.jp/contests/abc342/submissions/50616942)

長さNの文字列Sに対して、Q個の文字列置換を実行するという問題です。
さっきとは打って変わって、N, Qの制約条件が
```math
1≤N≤2×10^5, 
1≤Q≤2×10^5
```

となっていたので、これは愚直に解くと無理だろうなあと思っていたら案の定TLEになってしまいました。（実行時間は2213ms）
その時の解法はこんな感じです。

```haskell
main :: IO ()
main = do
  _ <- readLn @Int
  s <- BC.getLine
  q <- readLn @Int
  cds <- replicateM q readPairChar

  BC.putStrLn $ L.foldl' applyOperation s cds

applyOperation :: BC.ByteString -> (Char, Char) -> BC.ByteString
applyOperation s (c, d) = BC.map (\x -> if x == c then d else x) s

createMap :: [(Char, Char)] -> M.Map Char Char -> M.Map Char Char
createMap [] m = m
createMap ((c, d) : ops') m = createMap ops' (M.insert c d m)
```

クエリを`Data.Map`で作って`foldl`で回しています。
この解法だと、長さNの文字列にQ個のクエリを繰り返す実行するため、計算量は`O(NQ)`、つまり`4×10^10`オーダになります。これは厳しいですね。

結局解法がわからなかったので、Contest後に[公式の解法](https://atcoder.jp/contests/abc342/editorial/9356)を見ると解き方がわかりました。実はちょっと工夫が必要な問題です。

https://x.com/luckyowlman/status/1761387102900748360?s=20

解き方としては、最初に全アルファベット`[a..z]`の対応関係のマップを作っておいて、入力値を元にMapを更新していきます。

最初のマップはこんな感じです。

```haskell
let initMap = M.fromList [(c, c) | c <- ['a' .. 'z']]
```

これを使うと、以下のようなマップが作成できます。つまり、最初は何も変換しないマップが出来上がります。

```haskell
ghci> M.fromList [(c, c) | c <- ['a' .. 'z']]
fromList [('a','a'),('b','b'),('c','c'),('d','d'),('e','e'),('f','f'),('g','g'),('h','h'),('i','i'),('j','j'),('k','k'),('l','l'),('m','m'),('n','n'),('o','o'),('p','p'),('q','q'),('r','r'),('s','s'),('t','t'),('u','u'),('v','v'),('w','w'),('x','x'),('y','y'),('z','z')]
```

ここから、入力値を元にマップを更新していきます。
例えば、以下のような入力値が与えられた時に

```
r a
t e
d v
a r
```

このようにマップを更新していきます。
- `('r', 'r')`⇨ `('r', 'a')`
- `('t', 't')`⇨ `('t', 'e')`
- `('d', 'v')`⇨ `('r', 'a')`
- `('a', 'a')`⇨ `('a', 'r')`, `('r', 'a')`⇨ `('r', 'r')`

最後の行がポイントで、入力値を元に対応関係の表を先に作っておくことで初期値のアルファベットが最終的にどの値になるかのマップをこれで作ることができます。

これを使うと、TLEとなっていた解法が`O(NQ)`だったのに対して、`O(ρ(N+Q))`(ρはアルファベットの長さ26)になります。
ρは定数になるので、これは`O(N+Q)`となり`2×10^5 * 2 = 4×10^5`のオーダとなります。これならいけそうですね。

これを実装するとこのようになりました。`Data.Map`はTravaesalなので[map](https://hackage.haskell.org/package/containers-0.7/docs/Data-Map-Internal.html#v:map)を使ってkey-valueのvalueのみ更新できます。便利。

```haskell
applyOps :: M.Map Char Char -> [(Char, Char)] -> M.Map Char Char
applyOps = L.foldl' applyOp
  where
    applyOp m (c, d) = M.map (\x -> if x == c then d else x) m
```

結果は無事ACで、実行時間も1203msに短縮できました。

## 全体を振り返って

前回、今回の問題を見ていて気づいたのですが、アルゴリズムとは別に「計算量を抑える工夫が必要な問題」で詰まるケースが多そうです。
こういうのは実装で詰まるとそっちに脳のリソースが取られると厳しくなりそうなので、もっと実装をスムーズにできるようになるのが大事かなあと思いました。

とりあえず、地道に問題を解いてもっとHaskellと仲良くなろうと思います。