AtCoder Beginner Contest 399 振り返り

ABC399の振り返りです。

## 結果

ABの2完でした。

![スクリーンショット 2025-03-31 0.01.57.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/f04b85fd-5a87-48b7-8757-271a51ff36f3.png)

![スクリーンショット 2025-03-31 0.03.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/c1a02355-8a00-4c31-813d-03c932c58676.png)

## ふりかえり

### A問題

- 問題
  - https://atcoder.jp/contests/abc398/tasks/abc399_a
- 回答
  - https://atcoder.jp/contests/abc399/submissions/64288142

2つの文字列をzipして比較し、異なる文字の数をカウントすれば解けます

```haskell
main :: IO ()
main = do
  _ <- readLn @Int
  s <- getLine
  t <- getLine

  print $ foldl' (\acc (s, t) -> bool acc (acc + 1) (s /= t)) 0 $ zip s t
```

### B問題

- 問題
  - https://atcoder.jp/contests/abc398/tasks/abc399_b
- 回答
  - https://atcoder.jp/contests/abc399/submissions/64301470

降順ソートして、グルーピングします。
入力例の場合だと、

`[3 12 9 9]`

iを保持するために`zip [1..]`して降順ソートし、グルーピングすると

`[[(2, 12)], [[(3, 9), (4, 9)]], [(1, 3)]]`

となります。

iをkey, rankをvalueとしたIntMapを作ります。IntMapで作っておくと、`elems`した時にkeyの昇順でvalueを取得することができます。

valueはグループの数ずつ足してfoldしていけばよいので、コードは以下のようになります。

```haskell
main :: IO ()
main = do
  _ <- readLn @Int
  psg <- groupOn snd . sortOn (Down . snd) . zip [1 ..] <$> getInts

  let ans =
        fst $
          foldl'
            ( \(im', r) p ->
                let im'' = IM.fromList [(i, r) | (i, _) <- p]
                 in (IM.union im'' im', r + length p)
            )
            (IM.empty, 1)
            psg

  mapM_ print $ IM.elems ans
```

### C問題

- 問題
  - https://atcoder.jp/contests/abc398/tasks/abc399_c
- 回答 upsolved
  - https://atcoder.jp/contests/abc399/submissions/64341182 (dfs)
  - https://atcoder.jp/contests/abc399/submissions/64371618 (union find)

dfsもしくはunion-findで解くことができます。

dfsの場合は、探索中に訪問済みのノードに到達した時にカウントを増やすようにします。
グラフが複数に分断されている場合を考慮して、すべてのノードを始点にしてdfsを行います。
この時、始点が訪問済みの場合はskipするようにしておきます。そうすると、各ノードには一度しか訪問しないため、計算量は`O(n)`になります。（この全てのノードを始点にするのが思いつかず、時間ぎりぎり間に合いませんでした）

```haskell
main :: IO ()
main = do
  [n, m] <- getInts
  uvs <- replicateM m getInts

  let g = buildG (1, n) uvs
      cnt = dfs' g n

  print $ snd cnt - m

-- print $ cnt - m

{-- lib --}

-- 深さ優先探索（グラフ用）
type Graph = Array Int [Int]

type Edge = (Int, Int)

type Bounds = (Int, Int)

-- グラフ構築
buildG :: Bounds -> [[Int]] -> Graph
buildG bounds edges = accumArray (flip (:)) [] bounds edges'
  where
    edges' = concatMap (\[u, v] -> [(u, v), (v, u)]) edges

dfs' g n =
  foldl'
    ( \acc@(seen, cnt) idx ->
        bool (go g acc idx) acc (IS.member idx seen)
    )
    (IS.empty, 0)
    [1 .. n]
  where
    go g (seen, cnt) v
      | IS.member v seen = (seen, cnt + 1)
      | otherwise = foldl' (go g) (seen', cnt) next_vs
      where
        next_vs = g ! v
        seen' = IS.insert v seen
```

この問題は、グラフがいくつかの塊に分かれることから、`ある辺の両端のノードがどちらもunionに属している場合にカウントする`と捉えることができます。

この場合は、union-findとして解くことが可能です。

`ある辺の両端のノードがどちらもunionに属している`は、↓のような実装を持っていればそのまま解くことができます。

```haskell
sameUF :: UnionFind -> Int -> Int -> IO Bool
sameUF uf x y = (==) <$> getRoot uf x <*> getRoot uf y
```

全体のコードはこのような形になります。

```haskell
main :: IO ()
main = do
  [n, m] <- getInts
  uvs <- replicateM m getInts

  uf <- newUF (1, n)
  cnt <- newIORef (0 :: Int)

  forM_ uvs $ \[u, v] -> do
    same <- sameUF uf u v
    if same
      then modifyIORef' cnt (+ 1)
      else unit uf u v

  readIORef cnt >>= print

{-- lib --}

{-- union find --}
-- UnionFind 各ノードの親ノード 各ノードが属する木のsize
-- ノード番号をuniqなintとして持っておく
-- arrayを使って、各ノードに対応する親ノード、sizeが取得できるようにする
-- UnionFind (IOUArray lowerbound upperbound) (IOUArray parent size)
data UnionFind = UnionFind (IOUArray Int Int) (IOUArray Int Int)

newUF :: (Int, Int) -> IO UnionFind
-- (<*>) :: Applicative f => f (a -> b) -> f a -> f b を適用
-- IO (a -> b) -> IO a -> IO b となる
newUF (s, e) = UnionFind <$> newArray (s, e) (-1) <*> newArray (s, e) 1

getRoot :: UnionFind -> Int -> IO Int
getRoot uf@(UnionFind parent _) x = do
  p <- readArray parent x
  if p == (-1)
    then return x
    else do
      p' <- getRoot uf p
      writeArray parent x p' -- 経路圧縮
      return p'

-- union by size
unite :: UnionFind -> Int -> Int -> IO ()
unite uf@(UnionFind parent size) x y = do
  same <- sameUF uf x y
  when same $ return ()

  x' <- getRoot uf x
  y' <- getRoot uf y

  when (x' /= y') $ do
    sizeX <- readArray size x'
    sizeY <- readArray size y'

    if sizeX > sizeY
      then do
        writeArray parent y' x'
        writeArray size x' (sizeX + sizeY)
      else do
        writeArray parent x' y'
        writeArray size y' (sizeX + sizeY)

sameUF :: UnionFind -> Int -> Int -> IO Bool
-- (<*>) :: Applicative f => f (a -> b) -> f a -> f b を適用
-- IO (Int -> Bool) -> IO Int -> IO Bool となる
-- IO (== (root uf x)) <*> IO (root uf y) という形になる
sameUF uf x y = (==) <$> getRoot uf x <*> getRoot uf y
```

## 全体を振り返って

がんばります！(C問題解けたなあ、、)

## おまけ

今回もRustで解き直してみました。
自前のunion-findを使ってますが、ac-library-rsがあれば[dsu](https://github.com/rust-lang-ja/ac-library-rs/blob/eea0b2ac6b177fc09b706b4e727b3e62e6ef30e7/src/dsu.rs)を使って解けるとおもいm

- C
  - https://atcoder.jp/contests/abc399/submissions/64374256