AtCoder Beginner Contest 350 振り返り

AtCoderの振り返りです。[abc350](https://atcoder.jp/contests/abc350)の記事を書き忘れてたので、今回はその振り返りになります。

## 今回の結果

A,B 2完でした。

![スクリーンショット 2024-05-01 11.56.49.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/640dbecc-3c33-7afb-ad41-81424c91e466.png)

![スクリーンショット 2024-05-01 11.55.55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/b980a92e-5e27-1c34-295e-ba8bb79ad991.png)

## 各問題の振り返り

### A - Past ABCs

- [問題](https://atcoder.jp/contests/abc350/tasks/abc350_a)
- [自分の回答](https://atcoder.jp/contests/abc350/submissions/52558892)

特に悩むことはなかったです。リストからSetを作って`member`で存在チェックします。

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

  let s' = read @Int $ L.drop 3 s
      set = S.fromList $ [1 .. 315] ++ [317 .. 349]

  putStrLn $ if S.member s' set then "Yes" else "No"
```

### B - Dentist Aoki

- [問題](https://atcoder.jp/contests/abc350/tasks/abc350_b)
- [自分の回答](https://atcoder.jp/contests/abc350/submissions/52571490)

問題から、`奇数回出現したらその番号の歯が抜かれている` `偶数回出現したらその番号の歯が生やされている`と判断できます。なので、`accumArray`でカウントして`filter`で以下の様に書けます。

```haskell
main :: IO ()
main = do
  [n, _] <- readInputInts
  tq <- readInputInts

  let counts = L.length . filter odd . IA.elems $ IA.accumArray @UArray (+) (0 :: Int) (1, n) $ map (,1) tq

  print $ n - counts

```

この記事を書いていて気づいたのですが、この書き方の方が良さそうです。

```haskell
main :: IO ()
main = do
  [n, _] <- readInputInts
  tq <- readInputInts

  let counts = L.length . filter even . IA.elems $ IA.accumArray @UArray (+) (0 :: Int) (1, n) $ map (,1) tq

  print counts
```

### C - Sort

- [問題](https://atcoder.jp/contests/abc350/tasks/abc350_c)
- [自分の回答(upsolved)](https://atcoder.jp/contests/abc350/submissions/52629423)

最後まで解けずにタイムアップした問題です。
計算量を減らすために、値が存在するindex情報を保存し都度更新することがポイントになります。
データを保存して都度更新するにはmutableなデータ持っておく必要がありますが、全ての値がimmutableなHaskellではそのままではできません。

ですが、Haskellにはmutableなデータ構造を使用するための方法がいくつかあります。
詳しくは省略しますが、ここではmutableなArrayである[IOUArray](https://hackage.haskell.org/package/array-0.5.7.0/docs/Data-Array-IO.html)を使用します。(これは`IO`モナドの中で使用できる`MArray`になります。)

回答は以下の様な感じです。

```haskell
main :: IO ()
main = do
  n <- readLn @Int
  an <- readInputInts

  anArr <- newListArray @IOUArray (1, n) an
  pos <- newArray @IOUArray (1, n) (-1 :: Int)

  for_ (zip an [1 ..]) $ \(a, i) -> do
    writeArray pos a i

  res <- for [1 .. n] $ \a -> do
    -- aは今見ている位置と、値aの2つの意味がある。
    elemA <- readArray anArr a -- aの位置にいる要素を取得する
    posA <- readArray pos a -- 値aが存在する位置を取得する
    swapArray anArr a posA -- aの数列を更新する
    swapArray pos a elemA -- aの位置のメモを更新する
    return (a, posA)

  let res' = [(i, j) | (i, j) <- res, i /= j]

  print $ L.length res'
  forM_ res' (\(i, j) -> putStrLn $ show i ++ " " ++ show j)

swapArray :: (MArray a e m, Ix i) => a i e -> i -> i -> m ()
swapArray as i j = do
  !a <- readArray as i
  !b <- readArray as j
  writeArray as j a
  writeArray as i b
```

## 全体を振り返って

Haskellでメモ化を使うのに慣れていないので、まだまだ練習が必要そうです。

## おまけ

練習のためにRustで解き直してみました。
Rustだと手続き型と関数型を織り交ぜることができるので大分書き味が変わって面白いです。

- [A - Past ABCs](https://atcoder.jp/contests/abc350/submissions/52677292)
- [B - Dentist Aoki](https://atcoder.jp/contests/abc350/submissions/52707628)
- [C - Sort](https://atcoder.jp/contests/abc350/submissions/52727925)