# ABC370 振り返り
- [トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370） - AtCoder](https://atcoder.jp/contests/abc370)
- ABC 3完 (363) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc370)
![[スクリーンショット 2024-09-08 9.55.40.png]]
ABC370 でした。爆死しました 😭
1年振りぐらいに灰色パフォーマンスを取ってしまいました。
- A (灰) ··· 場合分けする
- B (灰) ··· 入力の読み取りが面倒だが、素直に問題文通りシミュレーションする
- C (灰) ··· 前から見て $S_i > T_i$ のものを最初に置換。そのあと後ろからみて $S_i \ne T_i$ のものを置換
- D (緑, upsolve) ··· 行ごとに順序付き集合で列番号、列ごとに順序付き集合で行番号、というデータ構造で壁の位置を管理
でした。
C 問題が、解法はすぐわかったのですがどうも実装をどこかミスっていて WA を繰り返してしまい、総崩れになってしまいました。
慌てて D に取り掛かりましたが、こちらも実装をミスして AC できず。実装精度を欠きました。
C は元々の実装のどこがまずかったのか未だによくわかってません 😓
## [A - Raise Both Hands](https://atcoder.jp/contests/abc370/tasks/abc370_a)
$L, R$ の値の組み合わせに応じて出力が変わります。パターンマッチで分解します。
```haskell
solve 1 1 = "Invalid"
solve 0 0 = "Invalid"
solve 1 0 = "Yes"
solve 0 1 = "No"
main :: IO ()
main = do
[l, r] <- getInts
putStrLn $ solve l r
```
## [B - Binary Alchemy](https://atcoder.jp/contests/abc370/tasks/abc370_b)
入力を読み取って二次元配列にします
入力から配列を構築する過程がやや面倒ですが、それができればあとは問題文通りに畳み込んでいくだけ
```haskell
main :: IO ()
main = do
n <- getInt
xss <- replicateM n getInts
let uvs = [[[((i, j), x), ((j, i), x)] | (j, x) <- indexed 1 xs] | (i, xs) <- indexed 1 xss]
as = accumArray @UArray (flip const) (-1 :: Int) ((1, 1), (n, n)) $ (concat . concat) uvs
ans = foldl' (\i j -> as ! (i, j)) 1 [1 .. n]
print ans
```
## [C - Word Ladder](https://atcoder.jp/contests/abc370/tasks/abc370_c)
前から見て $S_i > T_i$ のものを最初に置換。そのあと後ろからみて $S_i \ne T_i$ のものを置換、これでいけます。
文字列を配列にして、インデックス アクセスで前から、後ろからの探索を行う
`mapAccumL` を使うと、前半が終わったときの文字列の状態が戻り値に残るので、続けて後半を計算するのもスムーズです。
本番ではこれを `iterate` と `takeWhile` で書いたらどうも境界周りでミスったようで、沼りました。
落ち着いて実装を選択するべきでした。
```haskell
main :: IO ()
main = do
s_ <- getLine
t_ <- getLine
let n = length s_
s0 = listArray @UArray (1, n) s_
t = listArray @UArray (1, n) t_
let (s1, res1) = mapAccumL f s0 [1 .. n]
where
f s i
| s ! i > t ! i = do
let s' = s // [(i, t ! i)]
(s', Just (elems s'))
| otherwise = (s, Nothing)
let (_, res2) = mapAccumL f s1 [n, n - 1 .. 1]
where
f s i
| s ! i /= t ! i = do
let s' = s // [(i, t ! i)]
(s', Just (elems s'))
| otherwise = (s, Nothing)
let res = catMaybes $ res1 ++ res2
print $ length res
for_ res putStrLn
```
## [D - Cross Explosion](https://atcoder.jp/contests/abc370/tasks/abc370_d)
マスの個数自体は $4 \times 10^5$ 程度なので、すべての壁をグリッドに配置して状態を管理することは可能です。
ただし爆弾を置いたときに破壊される壁の位置を特定するのに、上下左右方向へ、二分探索的な探索ができる必要があります。
二次元配列で壁の位置を持ってしまうと、それができません。
そこで行と列を独立に考えて、行ごとに壁のある位置の列番号の順序付き集合、列ごとに壁のある位置の行番号の順序付き集合、というデータ構造を用意します。行、列それぞれに配列があって配列の要素が IntSet という構造です。
このデータ構造なら、壁位置の挿入と削除、ある位置から上下左右でもっとも近い壁の位置を探す、ということが可能です。
- 壁を削除する `erase` 関数を切り出しておく
- `IS.lookupGT` は `Maybe` を返すが、`Maybe` が Traversable なことを利用 ··· つまりアプリカティブファンクターと捉えて `for_` もしくは `traverse_` で「Just の場合だけ関数を適用する」を表現する
の二点を考慮するとシンプルに書けます。
本番でもこれぐらいシンプルに書くことを心掛けたほうが結果的には、慌てて沼らずに済んだと思いました。
C 問題もそうでしたが、あわててだだーっと書くと、だめですね 😓
```haskell
main :: IO ()
main = do
[h, w, q] <- getInts
qs <- replicateM q getTuple
hs <- newArray @IOArray (1, h) $ IS.fromList [1 .. w]
ws <- newArray @IOArray (1, w) $ IS.fromList [1 .. h]
let erase (i, j) = do
modifyArray hs i (IS.delete j)
modifyArray ws j (IS.delete i)
for_ qs $ \(i, j) -> do
a <- readArray hs i
b <- readArray ws j
if IS.member j a
then erase (i, j)
else do
for_ (IS.lookupGT j a) $ \j' -> erase (i, j')
for_ (IS.lookupLT j a) $ \j' -> erase (i, j')
for_ (IS.lookupGT i b) $ \i' -> erase (i', j)
for_ (IS.lookupLT i b) $ \i' -> erase (i', j)
hs' <- getElems hs
let ans = sum' [IS.size s | s <- hs']
print ans
```
## 感想など
ここ数回、負けこんでいてレートが総計で -100 されて 1040 まで落ちてしまいました。
数ヶ月分の累積が飛んでしまいました 😭
仕方がないですね。またコツコツ上げていこうかと思います。
ここ最近すこし精進をサボり気味なんですが、それが結果に出ているのでしょうか。