# ABC386 振り返り
- [AtCoder Beginner Contest 386 - AtCoder](https://atcoder.jp/contests/abc386)
- ABC 3完 (796) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc386)
![[スクリーンショット 2024-12-29 9.31.47.png]]
ABC386 でした。
D 問題を誤読して最後の最後まで、なんで入力例 4 が No なんだろうな〜、とわからないまま終わってしまいました。大敗。
- A (灰, 25) ··· バケットを作ってフルハウスになるパターンかを判定
- B (灰, 42) ··· 連長圧縮で `0` のときだけ $2$ で割る
- C (灰, 254) ··· $1$ 文字しか違わないので一致、置換、削除、挿入の 4パターンに分岐してそれぞれ判定
- D (緑, 996, upsolve) ··· イベントソート
でした。
## [A - Full House 2](https://atcoder.jp/contests/abc386/tasks/abc386_a)
$A, B, C, D$ に割り当てられた数字の出現頻度を数えて、フルハウス一歩手前かどうか。
色々やり方はありそうですが一番最初に思いついた割と愚直な方法で実装。
バケットを取って出現頻度がフルハウス手前のパターンになっているか、で判定。
```haskell
main :: IO ()
main = do
[a, b, c, d] <- getInts
let xs = sort' $ filter (/= 0) $ elems $ toBucket (1, 13) [a, b, c, d]
printYn $ xs == [1, 3] || xs == [2, 2]
```
## [B - Calculator](https://atcoder.jp/contests/abc386/tasks/abc386_b)
以前に同じ問題があったような?
`0` の場合だけ `00` キーで2回の操作を1回に短縮できるので、連長圧縮で `0` が続く長さを求めて 2 で `ceildiv` する。
```haskell
main :: IO ()
main = do
s <- getLine
let res = [if c == '0' then k `ceildiv` 2 else k | (c, k) <- rle s]
print $ sum' res
```
## [C - Operate 1](https://atcoder.jp/contests/abc386/tasks/abc386_c)
$S$ と $T$ の編集距離が $1$ 以内かを求めよ、という問題ですが文字列がそこそこ大きいので編集距離 DP は使えない。
これも以前に似たような問題があったような。
- $S = T$ のときは当然、真
- $|S| = |T|$ で $1$ 文字しか違わないときは、真
- 文字列の長さの差が $1$ だけのときは、先頭から見ていって文字が違ってるところを削除。そこから後ろが一致してるかどうかで、挿入 / 削除で同じになるかを判定
というのを場合分けで実装しました。
```haskell
solve s t
| s == t = True
| n == m && countBy (== False) (zipWith (==) s t) == 1 = True
| n - m == 1 = do
-- 削除
let i = length $ takeWhile (\(a, b) -> a == b) $ zip s t
s' = deleteAt i s
s' == t
| m - n == 1 = do
-- 挿入
let i = length $ takeWhile (\(a, b) -> a == b) $ zip s t
t' = deleteAt i t
s == t'
| otherwise = False
where
n = length s
m = length t
main :: IO ()
main = do
k <- getInt
s <- getLine
t <- getLine
printYn $ solve s t
```
ところで、最初は上記の方法ではなく前と後ろから文字の一致数を見ていくという方法で実装しました。
が、 2 WA をもらい「んー?」と思いながら前述の方針に変更。
以下で AC できました。WA をもらったのは $l + r = M$ と等号で判定していたからでした。`s = aaaa` `t = aaaaa` のときを考慮すると $l + r \geq M$ としておかないと駄目でした。
実装の変更と 1 ペナで 15分程度ロス。
```haskell
solve s t
| s == t = True
| n == m && countBy (== False) (zipWith (==) s t) == 1 = True
| n - m == 1 = l + r >= m
| m - n == 1 = l + r >= n
| otherwise = False
where
n = length s
m = length t
l = length $ takeWhile (== True) $ zipWith (==) s t
r = length $ takeWhile (== True) $ zipWith (==) (reverse s) (reverse t)
main :: IO ()
main = do
k <- getInt
s <- getLine
t <- getLine
printYn $ solve s t
```
## [D - Diagonal Separation](https://atcoder.jp/contests/abc386/tasks/abc386_d) (upsolve)
問題の解釈を最後の最後まで間違えていました。
`B` があったらその上と左が全部 `B` になる、と誤解していましたが正しくは `B` があったら左上の区画全部が `B` になる、でした。とほほ
![[Pasted image 20241229095111.png|300]]
この `B` で左上が黒くなるのに対して `W` がそれを邪魔する位置にあってはいけない、という問題でした。
![[Pasted image 20241229095205.png|400]]
`W`からみると右下の領域が白くなるわけですがそこに `B` があってもいけない。
![[Pasted image 20241229095252.png|400]]
上図のケースを考えると、行を上からみていったときに `W` が登場すると、以降 `B` を置ける位置に制約がかかることがわかります。
`W` が登場した位置よりも左側に `B` がないと NG です。
90度左に倒してみると、よりわかりやすいでしょうか。
![[Pasted image 20241229095512.png|600]]
左からみていったときに `W` が低い位置で登場すると、もう `B` は以降、その `W` の低い位置以降にしか登場できません。そう出ない場合は矛盾が生じます。
この問題は Yes or No が問われているだけの問題なので、この矛盾があるかないかを調べれば OK
- $(x, y)$ でソートしてより左上にあるマスから順に見ていく
- `W` が登場した $y$ の最小値を状態として管理する。初期値は $y = \infty$
- `B` が登場したらその $y$ の最小値と比較してそれより小さければ問題なし
これを $M$ 個のマス全てに試して、矛盾がなければ Yes です。
```haskell
main :: IO ()
main = do
[_, m] <- getInts
items <- replicateM m $ auto @(Int, Int, Char)
let (_, res) = mapAccumL f maxBound (sort items)
where
f acc (_, y, 'B') = (acc, y < acc)
f acc (_, y, 'W') = (min acc y, True)
printYn $ and res
```
二次元の図形問題を、イベントソートの問題に転換して解く、という問題でした。
イベントソートをこういう用途に適用できるという発想がなく、問題を改めて理解したのち考えてみましたがさっとは解けませんでした。
二次元のルールや制約を「ソートで一方向に走査 +もう一方の次元を境界管理」するパターンと言えるようです。
区間スケジューリング問題や、いもす法のように線分を数直線上に投影して管理、なども同じような抽象に辿りつきそう。
イベントソートの問題を特訓して、このメンタルモデルを獲得したいところです。
## 感想など
年内最後のコンテストということで、勝ってあわよくば入水と思っていたのですが、大きく負けてレートは -32
入水が遠のきました。またここから 3 〜 4回 水パフォを取る必要がありそうです。三歩進んで二歩下がる。
問題を誤読してしまったのは仕方がないとして、イベントソートのような、やや出題頻度の低いアルゴリズムに対して抽象的理解がいまいち進んでいないことがよくわかりました。
DP やグラフ探索、Union-Find、二分探索、セグメント木などの問題は数多く解いていることもあり、アルゴリズムをより抽象的に理解できていて、その類の問題は多少問題文の表面からそのアルゴリズムの匂いがしなくても、直感的に見極めることができていると思います。
アルゴリズム理解の抽象度の低いものではそこが直結しておらず、D 問題のようなものをみても、イベントソートを使うなどの発想に全く至らない感があります。
緑、水色下位のアルゴリズムで抽象的理解が足りてないものが幾つか思い当たるので、しばらくそれらを集中的に復習してみようと思います。
というわけで 2024 年は入水ならず、レート 1141 で〆でした。
良いお年を〜