AtCoder Beginner Contest 340 振り返り

書くの忘れてましたが前々回のABC振り返りです。
※前回の記事は[ここ](https://qiita.com/flowerhill/items/db14b77e40825008314a)

## 今回の結果

A,B 2完でした。

![スクリーンショット 2024-02-23 0.01.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/cd131603-452f-a713-7f19-b621dba71c61.png)


## 各問題の振り返り

### A - Arithmetic Progression

- [問題](https://atcoder.jp/contests/abc340/tasks/abc340_a)
- [自分の回答](https://atcoder.jp/contests/abc340/submissions/50150945)

等差数列を順番出力する問題。Haskellはリストでこういう書き方ができるので便利ですね。

```haskell
main :: IO ()
main = do
  [!a, !b, !d] <- readInputInts

  putStrLn $ unwords $ map show [a, a + d .. b]

readInputInts :: IO [Int]
readInputInts = L.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine

```

### B - Append

- [問題](https://atcoder.jp/contests/abc340/tasks/abc340_b)
- [自分の回答](https://atcoder.jp/contests/abc340/submissions/50168985)

query通りに操作して回答のリストに追加していって、最後にreverseしてunwordsしました。

今考えるとqueryを処理する中で出力した方が筋の良い回答だったかもしれません

### C - Divide and Divide

- [問題](https://atcoder.jp/contests/abc340/tasks/abc340_c)
- 自分の回答
  - [IORef使用版](https://atcoder.jp/contests/abc340/submissions/50204685)
  - [STRef使用版](https://atcoder.jp/contests/abc340/submissions/50205315)
  - [Stateモナド使用版](https://atcoder.jp/contests/abc340/submissions/50205753)

メモ化を使う発想にならなかったのもありますが、メモ化は状態を引き回す必要があるので、Haskellでやるには工夫が必要で難しかったです。
Haskellでメモ化を使うには、ミュータブルな状態を持つことになるのでIORef, STRefのいずれかを使うことになります。（Stateモナドでも実装可能です。

まずメモ用のIntMapを初期化します。。1はスコア0なので、こんな感じになります。

```haskell
 memo <- newIORef (IM.singleton 1 0)
```

で、IntMapから取得した結果がJustかNothingかで処理を分けます。
Nothingの場合: メモ化したデータがなかったということなので、新しくデータを取得して追加します。`modifyIORef'`でIORefのデータを変更します。

```haskell
 modifyIORef' memo $ IM.insert x (x + s + t)
```

次に、メモ化のIntMapから取得した値がJust/Nothingどちらを取るかで処理を分けます。
大体こんな感じです。
- Justの場合: メモ化した値が取得できたMapから取得したデータをそのまま返す
- Nothingの場合、計算してメモに追加

Nothing, Justの分岐は`maybe`メソッドを使うと便利です。
シグネチャは以下の通りです。引数のMaybeがNothingだとbを返し、Justだとaに(a -> b)を適用した値を返します。

```haskell
 maybe :: b -> (a -> b) -> Maybe a -> b
```
これを使って実装するとこうなります。
```haskell
 main :: IO ()
 main = do
   n <- readLn @Int
   memo <- newIORef (IM.singleton 1 0)
 
   let f x = do
         v <- readIORef memo
         let u = IM.lookup x v
         maybe
           ( do
               s <- f (x `div` 2)
               t <- f (if even x then x `div` 2 else x `div` 2 + 1)
               modifyIORef' memo $ IM.insert x (x + s + t)
               return (x + s + t)
           )
           return
           u
 
   f n >>= print  
```
f xが`Int -> IO Key` のシグネチャを持っており、`IO Key`型のデータを返すので、printに渡す時にはbindする必要があります。

STモナドの場合
STモナドのシグネチャはこうです。 `s`はいわゆる幽霊型になります。
```haskell
 data ST s a
```

これを使って実装すると、こうなります。基本的な実装はIORefと同じですが、STの中でしか使えないので、別の関数に切り出す必要があります。
```haskell
 main :: IO ()
 main = do
   n <- readLn @Int
   print $ runST (f n)
 
 f :: Int -> ST s Int
 f n = do
   memo <- newSTRef (IM.singleton 1 0)
   let g x = do
         v <- readSTRef memo
         let u = IM.lookup x v
         maybe
           ( do
               s <- g (x `div` 2)
               t <- g (if even x then x `div` 2 else x `div` 2 + 1)
               modifySTRef' memo $ IM.insert x (x + s + t)
               return (x + s + t)
           )
           return
           u
   g n
```

STを実行する場合は`runST`を使用します。

runSTのシグネチャはこうなります。
```haskell
 runST :: (forall s. ST s a) -> a
```

これは値のみを返すのみなのでprintに渡す時bindする必要はありません。

最後に、Stateモナドを使った実装例を紹介します。

```haskell
 main :: IO ()
 main = do
   !n <- readLn @Int
   let !res = execState (f n) $ IM.singleton 1 0
   print $ res IM.! n
 
 f :: Int -> State (IM.IntMap Int) Int
 f 1 = return (0 :: Int)
 f n = do
   !v <- gets $ IM.lookup n
   maybe
     ( do
         !s <- f (n `div` 2)
         !t <- f (if even n then n `div` 2 else n `div` 2 + 1)
         modify' $ IM.insert n (n + s + t)
         return (n + s + t)
     )
     return
     v
 ```

STRefを使うと2msだったのですが、Stateモナドだと1msで何故か少し早くなりました。


## 全体を振り返って

今回2完でしたが、メモ化を通してSTRefやIORef, Stateモナドの使い方を勉強できたので面白かったです。
Haskellのメモ化はなかなか難しいなと少し思いました。