AtCoder Beginner Contest 341 振り返り

遅くなりましたが、341の振り返りです。
前回の記事は[ここ](https://qiita.com/flowerhill/items/890cf7acf2bd08a95884)
## 今回の結果

A,C 2完でした。

![スクリーンショット 2024-02-24 17.52.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/ea80a49b-827b-a31e-b24a-ea5c391404cc.png)

![スクリーンショット 2024-02-24 17.53.52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/8e64c6cf-657d-f359-f845-a62ae0e7eadc.png)

## 各問題の振り返り

### A - Print 341 

- [問題](https://atcoder.jp/contests/abc341/tasks/abc341_a)
- [自分の回答](https://atcoder.jp/contests/abc341/submissions/50348528)

文字を繰り返し出力する問題。`replicate`を使ってリピートし、`concat`で繋げます。

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

  putStrLn $ concat $ "1" : replicate n "01"
```

### B - Foreign Exchange (upsolved)

- [問題](https://atcoder.jp/contests/abc341/tasks/abc341_b)
- [自分の回答(upsolved)](https://atcoder.jp/contests/abc341/submissions/50394913)

通貨を交換していく問題。
最初は通貨を一つづつ交換していく実装をしていたのですが、手元で実行したところ時間がかかりすぎたので断念しました。

あとで[解説](https://atcoder.jp/contests/abc341/editorial/9317)を確認すると

```
国i の通貨をAi単位持っているとき、国i の通貨から国i+1 の通貨への交換ができる回数は⌊Ai/Si⌋ 回とわかるので、⌊Ai/Si⌋ 回の交換をまとめて行って国
i+1 の通貨が⌊Ai/Si⌋×Ti単位得られるとして良いです。
```

と書いてあったので、これを使ってupsolveしました。

```haskell
main :: IO ()
main = do
  n <- readLn @Int
  as <- readInputInts
  sts <- replicateM (n - 1) readPairInt

  print $ solve (init as) sts (last as)

solve :: [Int] -> [(Int, Int)] -> Int -> Int
solve [a] [(s, t)] res = res'
  where
    count = a `div` s
    res' = res + count * t
solve (a : a' : as') ((s, t) : sts') res = solve (a'' : as') sts' res
  where
    count = a `div` s
    a'' = a' + count * t
```

### C - Divide and Divide

- [問題](https://atcoder.jp/contests/abc341/tasks/abc341_c)
- [自分の回答](https://atcoder.jp/contests/abc341/submissions/50385786)

グリッドの移動可能かどうかを判定する問題です。こういう時は`Array`が便利で、Arrayを使って愚直に解きました。

```haskell
main :: IO ()
main = do
  [h, w, n] <- readInputInts
  moves <- getLine
  ss <- replicateM h getLine

  let grid = listArray @UArray ((1, 1), (h, w)) $ concat ss

  print $ length $ filter (possiblePositions grid moves) (indices grid)

type Grid = UArray (Int, Int) Char

type Position = (Int, Int)

possiblePositions :: Grid -> String -> Position -> Bool
possiblePositions grid = inner
  where
    inner [] point = isLand grid point
    inner (m : moves') point =
      isLand grid point && inner moves' (move point m)

isLand :: Grid -> Position -> Bool
isLand grid pos = inRange (bounds grid) pos && (grid ! pos) == '.'

move :: (Int, Int) -> Char -> (Int, Int)
move (i, j) 'L' = (i, j - 1)
move (i, j) 'R' = (i, j + 1)
move (i, j) 'U' = (i - 1, j)
move (i, j) 'D' = (i + 1, j)
move pos _ = pos
```

この解法だと枝刈りしておらず、パフォーマンスが低いため、本来は枝刈りして高速化した方が良いです。その場合はこのようになります。(回答の全体は[ここ](https://atcoder.jp/contests/abc341/submissions/50397279)にあります。)

```haskell
main :: IO ()
main = do
  [h, w, n] <- readInputInts
  moves <- getLine
  ss <- replicateM h getLine

  let grid = listArray @UArray ((1, 1), (h, w)) $ concat ss

  print $ length $ filter (possiblePositions grid moves) (indices grid)

type Grid = UArray (Int, Int) Char

type Position = (Int, Int)

possiblePositions :: Grid -> String -> Position -> Bool
possiblePositions grid = inner
  where
    inner [] point = isLand grid point
    inner (m : moves') point =
      isLand grid point && inner moves' (move point m)

isLand :: Grid -> Position -> Bool
isLand grid pos = inRange (bounds grid) pos && (grid ! pos) == '.'

move :: (Int, Int) -> Char -> (Int, Int)
move (i, j) 'L' = (i, j - 1)
move (i, j) 'R' = (i, j + 1)
move (i, j) 'U' = (i - 1, j)
move (i, j) 'D' = (i + 1, j)
move pos _ = pos
```

これにより、実行時間が `2171 ms`から`1581 ms`に短縮されました。

## 全体を振り返って

今回のB問題は解けた問題だったなと少し反省しています。
次は3完できるといいな。