# ABC391 振り返り
- [AtCoder Beginner Contest 391 - AtCoder](https://atcoder.jp/contests/abc391)
- ABCDE 5完 (1298) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc391)
![[スクリーンショット 2025-02-02 8.33.32.png]]
- A (灰, 10) ··· 四方の反対の方角を定義して、 文字列を map する
- B (灰, 110) ··· $T$ を動かして $S$ に一致するか、を全探索
- C (灰, 209) ··· 鳩の位置の配列、各巣にいる鳩の数の配列、$2$ 匹以上入ってる巣の数のスカラーを用意してシミュレーション
- D (緑, 924) ··· 各ブロックが削除されるタイミングを計算する。列ごとに整理して `transpose` するとよい
- E (緑, 1165) ··· 3分木を畳み込んでいく計算。根を $0$ にするための最小コスト、$1$ にするための最小コストを両方もって計算するよう畳み込んでいけばよい
## [A - Lucky Direction](https://atcoder.jp/contests/abc391/tasks/abc391_a)
`NE` や `NW` の反対まで定義すると面倒なので、四方の反対を定義して済ませる
```haskell
solve c = case c of
'N' -> 'S'
'E' -> 'W'
'W' -> 'E'
'S' -> 'N'
main :: IO ()
main = do
d <- getLine
putStrLn $ map solve d
```
## [B - Seek Grid](https://atcoder.jp/contests/abc391/tasks/abc391_b)
「$T$ を動かして $S$ に一致するか」と考える。$T$ を動かす範囲は $S$ の大きさ分。ただし $T$ の右下が $S$ の範囲からはみ出るケースは無視。
最初、`#` のある位置だけ一致すればいいやと、横着して集合で計算しようとしましたが `.` も一致をみる必要があることに気づいて実装しなおし。
すこし時間をロスしました。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
s <- getCharGrid ((1, 1), (n, n))
t <- getCharGrid ((1, 1), (m, m))
let vs = range (bounds t)
res =
[ d
| d <- range ((0, 0), (n, n)),
let us = map (+ d) vs,
inRange (bounds s) (maximum us),
and $ zipWith (\v u -> t ! v == s ! u) vs us
]
ans = head res
printTuple $ (1, 1) + ans
```
## [C - Pigeonhole Query](https://atcoder.jp/contests/abc391/tasks/abc391_c)
特に複雑なデータ構造は必要なく、鳩がどこにいるか? 各巣にその時点で何匹いるか? $2$ 匹を超えている巣 $acc$ がいくつあるか? を管理してシミュレーション
巣に鳩が移動して $2$ になったら、$acc + 1$ で、出ていって $1$ になったら $acc - 1$ とする。
配列をごりごりに更新することにるので、全体的に手続き型プログラミングにする方が楽、ということで IORef と IOUArray で実装する。
```haskell
main :: IO ()
main = do
[n, q] <- getInts
qs <- replicateM q getInts
accRef <- newIORef (0 :: Int)
place <- newListArray @IOUArray (1, n) [1 .. n]
count <- newArray @IOUArray (1, n) (1 :: Int)
for_ qs $ \case
[1, p, h] -> do
prevPlace <- readArray place p
writeArray place p h
modifyArray count h (+ 1)
modifyArray count prevPlace (+ (-1))
prevC <- readArray count prevPlace
newC <- readArray count h
when (prevC == 1) $ do
modifyRef' accRef (+ (-1))
when (newC == 2) $ do
modifyRef' accRef (+ 1)
[2] -> print =<< readIORef accRef
_ -> error "Invalid"
```
## [D - Gravity](https://atcoder.jp/contests/abc391/tasks/abc391_d)
ぱっと見時間がかかりそう、かつ E の方がわりとスムーズに解法が思いついたので飛ばして E を先に解いてから戻ってきました。
![[atcoder/images/IMG_2714.jpeg|600]]
上図のように適当にブロックを並べてみて、削除される順番を書き込んでみます。気がつくことが幾つかあります。
- 3段目以降のブロックは削除されることはない。各列ごとにブロックの段数をとって、最小の段数 $K$ が削除されるブロックの行数
- $i$ 回目に削除されるブロックの削除タイミング $t_i$ は、同じ $i$ 回目に削除されるブロックのうちもっとも上にあるブロックの高さ $y$ によって決まる
というわけで、各ブロックの削除タイミング $t$ を求めることで、問題の答えに回答できそう。
- 各列ごとに $y$ をリストに整理する
- 何段削除されるか $K$ を求めて、先のリストを全て `take k` する
- これを `transpose` すると同じタイミングで削除されるブロックをまとめることができる (!)
- 同じ削除タイミングでまとまったブロックのうち $y$ が一番大きいものを、そのブロック群の削除タイミングとする
これで OK です。 `transpose` すればよいことに気づけると実装がかなり楽になります。
本番ではそこに気がつかず、かなり沼りました。
```haskell
main = do
[n, w] <- getInts
blocks <- replicateM n getTuple
q <- getInt
qs <- replicateM q getTuple
let blocks' = [(x, y - 1, i) | (i, (x, y)) <- indexed 1 blocks]
cols = amap sort' $ accumArray @Array (flip (:)) [] (1, w) [(x, (i, t)) | (x, t, i) <- blocks']
k = minimum $ amap length cols
rows = transpose $ elems (amap (take k) cols)
ts = accumArray @UArray (flip const) maxBound (1, n) $ concat [[(i, t) | (i, _) <- row] | row <- rows, let (_, t) = maximumOn snd row]
for_ qs $ \(t, a) -> do
printYn $ t <= ts ! a
```
## [E - Hierarchical Majority Vote](https://atcoder.jp/contests/abc391/tasks/abc391_e)
3分木を根に向かって畳み込んでいく問題です。その構造が頭に描けると比較的スムーズ。
根への畳み込み回数は $N$ 回です。
$0$ から $1$ へ変える... という話をいったん忘れて、根まで多数決を取りながら畳み込んでいった結果、根が $0$ or $1$ いずれになるか?
は以下のように書けます。
```haskell
let root = head $ times n f as
where
toTriple xs = [(a, b, c) | [a, b, c] <- chunksOf 3 xs]
f xs = [if (length . filter (== '0')) [a, b, c] >= 2 then '0' else '1' | (a, b, c) <- toTriple xs]
```
値をトリプルにまとめて、多数決の結果を $1$ 値に畳み込んでいくのを $N$ 回繰り返す。
次に、書き換えのことを考えます。
各要素を $0$ にするコスト、$1$ にするコストを $(cost0, cost1)$ というタプルに表現して、これを根まで畳み込んでいくと最終的に根を $0$ にするときの最小コスト、根を $1$ にするときの最小コストを求めることがでます。
問題は $3$ 値の結合処理ですが、例えば $0$ にするなら $2$ 値が $0$ のとき $3$ 値目は $0$ or $1$ のどちらでもよいわけですから、$2$ 値が $0$ コストに $3$ 値目が $0$ or $1$ の小さい方というのを全パターン試して最小を取れば良い。
理解は、実装をみる方がはやいと思います。
これで根を $0$ にするための最小コスト、$1$ にするための最小コストが求められる。
このとき、たとえば何も書き換えなければ根が $0$ の場合、根を $0$ にするコストは $0$ になっているはず。
答え $0$ or $1$ にするための最小コストのうち、$0$ ではない方、つまり大きい方です。
```haskell
toTriple xs = [(a, b, c) | [a, b, c] <- chunksOf 3 xs]
main :: IO ()
main = do
n <- getInt
as <- getLine
let res = times n f [if a == '0' then (0, 1) else (1, 0) | a <- as]
where
f xs = [combine a b c | (a, b, c) <- toTriple xs]
combine (a0, a1) (b0, b1) (c0, c1) = do
let x1 = a0 + b0 + min c0 c1
x2 = a0 + c0 + min b0 b1
x3 = b0 + c0 + min a0 a1
v0 = minimum [x1, x2, x3]
let y1 = a1 + b1 + min c0 c1
y2 = a1 + c1 + min b0 b1
y3 = b1 + c1 + min a0 a1
v1 = minimum [y1, y2, y3]
(v0, v1)
let (cost0, cost1) = head res
print $ max cost0 cost1
```