AtCoder Beginner Contest 337 振り返り

遅くなりましたが、前回のABC振り返りです。

※前回の記事はこちら
https://qiita.com/flowerhill/items/d5f9f6b81d42ce81ca95

## 今回の結果

今回はA,B 2完でした。成長しない。。

![スクリーンショット 2024-01-23 18.43.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/53e165b4-7142-9a1a-bd63-d2a72014bf99.png)

![スクリーンショット 2024-01-23 18.44.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/2bc2402e-fd4b-c010-8bf8-5cf7ca14956d.png)


## 各問題の振り返り

### A - Scoreboard

- [問題文](https://atcoder.jp/contests/abc337/tasks/abc337_a)
- [自分の回答](https://atcoder.jp/contests/abc337/submissions/49449111)

XとYがN回試合をして、scoreを多く取った方を出力する問題です。
`fold`して比較すれば解けます。

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

  let (xTotal, yTotal) = L.foldl' (\(xAcc, yAcc) (x, y) -> (xAcc + x, yAcc + y)) (0, 0) scores

  putStrLn if xTotal > yTotal then "Takahashi" else if xTotal < yTotal then "Aoki" else "Draw"
```

### B - Extended ABC

- [問題文](https://atcoder.jp/contests/abc337/tasks/abc337_b)
- [自分の回答](https://atcoder.jp/contests/abc337/submissions/49480886)

拡張ABC文字列を判定する問題です。拡張文字列とは`A`,`B`,`C`がこの順番で並んでいる文字列のことを指します。
例えば`AABBCCCC`は拡張ABC文字列ですが、`AABACCCC`は拡張ABC文字列ではありません。

解答ですが、本番ではかなり愚直に解きました。`BS.group`を使って文字列をグループ分けし、グループ分け後の配列のサイズで以下のように場合分けしました。

- サイズが1の場合: `"A" || "B" || "C"`
- サイズが2の場合: `"AB" || "BC" || "AC"`
- サイズが3の場合: `"ABC"`

グループ分けすると、配列が`["AA", "BBB", "CCCC"]`のようになるので、`isPrefixOf`を使って先頭のみ抽出しています。

ちなみに、条件を間違えて2ペナ食らいました。

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

  putStrLn $ judge $ BS.group s

judge :: [BS.ByteString] -> String
judge g
  | null g = "Yes"
  | length g == 1 = if isPrefixOfA (head g) || isPrefixOfB (head g) || isPrefixOfC (head g) then "Yes" else "No"
  | length g == 2 = if isPrefixOfA (head g) && isPrefixOfB (g !! 1) || isPrefixOfB (head g) && isPrefixOfC (g !! 1) || isPrefixOfA (head g) && isPrefixOfC (g !! 1) then "Yes" else "No"
  | length g == 3 = if isPrefixOfA (head g) && isPrefixOfB (g !! 1) && isPrefixOfC (g !! 2) then "Yes" else "No"
  | otherwise = "No"
  where
    isPrefixOfA = BS.isPrefixOf (BS.pack "A")
    isPrefixOfB = BS.isPrefixOf (BS.pack "B")
    isPrefixOfC = BS.isPrefixOf (BS.pack "C")
```

他の人の回答を見て知ったのですが、この問題はもっと簡単に解くことができます。
ここでは2つ例を挙げます。

- ソート後と前が同じならば拡張ABC文字列と判定する

```haskell
module Main where

import qualified Data.ByteString as BS

main :: IO ()
main = do
  s <- BS.getLine

  putStrLn $ if BS.sort s == s then "Yes" else "No"
```

- `'A'`, `'B'`, `'C'`の順番で文字列をdropWhileして空文字なら拡張ABC文字列と判定する。

```haskell
module Main where

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

  let s1 = dropWhile (== 'C') $ dropWhile (== 'B') $ dropWhile (== 'A') s

  putStrLn $ if s1 == "" then "Yes" else "No"
```


### C - Lining Up 2

- [問題文](https://atcoder.jp/contests/abc337/tasks/abc337_c)
- [自分の回答(WA)](https://atcoder.jp/contests/abc337/submissions/49477966)
    - [upsolved](https://atcoder.jp/contests/abc337/submissions/49515234)

以下の数列が与えられた時、列を作る問題です。
```math
A_1, A_2,.., An 
```

列の作り方は`Ai = j`のように値が与えられているので、`Ai`が`Aj`の後ろに並ぶように作ります。
また、先頭は`Ai = -1`となる`A`になります。

先頭を探すのは難しくないのですが、`Ai`の後ろに並ぶ値`Aj`を探すとき、`Aj = i`となる`A`を毎回探すと、
毎回`Ai`に対応する`Aj`を探すことになるので計算量が`O(n^2)`となってしまいます。

問題の制約を見ると

```math
1≤N≤3×10^5
```

となっているため、これだとTLEになりそうです。自分は二分探索かなーと思ったのですが、これだとうまく解けずにWAとなってしまいました。

正解はもっと単純に`IntMap`(HaskellのHashMapみたいなもの。keyがintegerになる。)を使えばよくて、これを使って先頭から列を作っていきます。

まずはこのように`IntMap`を作ります。これで、`A`のリストがkey, 区間`[1, n]`の値がvalueになります。

```haskell
let asMap = IM.fromList $ zip as [1 ..]
```

この後は、`-1`を起点にして、次の要素をたどりながら列を作っていきます。
valueの値をkeyに指定している要素が次に後ろに並ぶ要素になるので、valueをkeyにして連結すると求める列が作れます。

```haskell
solve :: IM.IntMap Int -> Int -> [Int]
solve map key
  | IM.member key map = val : solve map val
  | otherwise = []
  where
    val = map IM.! key
```

全体像はこんな感じです。

```haskell
module Main where

import qualified Data.ByteString.Char8 as BS
import Data.Char (isSpace)
import qualified Data.IntMap as IM
import qualified Data.List as L
import Debug.Trace (traceShow, traceShowId)

main :: IO ()
main = do
  getLine
  as <- L.unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

  let asMap = IM.fromList $ zip as [1 ..]

  putStrLn $ unwords . map show $ solve asMap (-1)

solve :: IM.IntMap Int -> Int -> [Int]
solve map key
  | IM.member key map = val : solve map val
  | otherwise = []
  where
    val = map IM.! key
```

## 全体を振り返って

なかなかレートが上がらずもどかしいですが、少し要領をつかめて来た気がしています。ただC問題は`IntMap`使えばいいことに気付けば解けたので、若干悔しい思いはあります。

悔しい気持ちはありつつも、焦らず一つ一つ理解して進めて行けたらいいなあと思っています。