# ABC380 振り返り
- [AtCoder Beginner Contest 380 - AtCoder](https://atcoder.jp/contests/abc380)
- 成績: ABCD 4完 (1113) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc380)
![[スクリーンショット 2024-11-18 8.12.38.png]]
ABC380 でした。
E 問題は解法はあっていたもものの実装力が求められる問題で、通しきれず。惜敗となりました。
- A (灰) ··· 件数を数えてもよいが、ソートして `122333` になるかを確認する方が楽
- B (灰) ··· 連長圧縮して `-` の区間長を求める
- C (灰) ··· 連長圧縮して $K$ 番目の `1` の塊を探し、手前の要素と swap する
- D (緑) ··· 特定位置の文字に着目すると、反転するかしないかは二分木でモデル化できる。二分木で何回、右の枝を辿ったか? で反転回数が分かる → `popcount`
- E (水, upsolve) ··· 同じ色でくっついた区間を Union-Find で管理。各代表元の左右の頂点、現在の色等も管理してクエリの度、左右と連結するかどうか判定する
## [A - 123233](https://atcoder.jp/contests/abc380/tasks/abc380_a)
$N$ を桁ごとにばらして出現回数を数える、でもよいが、条件を満たす文字列はソートすると必ず `122333` になるのでそれを利用します。
```haskell
main :: IO ()
main = do
n <- getLine
printYn $ sort n == "122333"
```
## [B - Hurdle Parsing](https://atcoder.jp/contests/abc380/tasks/abc380_b)
連長圧縮して `-` のところだけを残す実装が楽そう、というわけでそうしました。
```haskell
main :: IO ()
main = do
s <- getLine
let res = [k | (c, k) <- rle s, c == '-']
printList res
```
なお `rle` は盆栽にある連長圧縮の関数で、Haskell なら一行で書けます
```haskell
rle :: (Eq a) => [a] -> [(a, Int)]
rle = map (\x -> (head x, length x)) . group
```
## [C - Move Segment](https://atcoder.jp/contests/abc380/tasks/abc380_c)
B 問題に続きこの問題も `0` と `1` それぞれ連続する区間をブロックにして扱うと楽そう。連長圧縮する。
その上で `1` の塊に左から順に番号を付けていき、$K$ 番目のブロックが何ブロック目かを探す。
その上で $K - 1$ 番目のブロックと入れ換えてから、連長圧縮を復元で OK。
なお、スワップを実装するのが面倒だったので、一度 Array に入れて盆栽済みの関数 `swapIArray`でやりました。
```haskell
main :: IO ()
main = do
[n, k] <- getInts
s <- getLine
let (_, res) = mapAccumL f 1 [(c, v) | (c, v) <- rle s]
where
f acc ('0', v) = (acc, ('0', v, acc))
f acc ('1', v) = (acc + 1, ('1', v, acc))
i = succ . fromJust $ findIndex (\(c, _, i) -> c == '1' && i == k) res
xs = listArray @Array (1, length res) res
xs' = swapIArray xs (i - 1) i
let ans = concat [replicate v c | (c, v, _) <- elems xs']
putStrLn ans
```
```haskell
swapIArray :: (IArray a e, Ix i) => a i e -> i -> i -> a i e
swapIArray as i j = as // [(i, as ! j), (j, as ! i)]
```
## [D - Strange Mirroring](https://atcoder.jp/contests/abc380/tasks/abc380_d)
なかなか面白い問題でした。
大文字小文字を反転した文字を後ろにつけていく操作を再帰的に、ほぼ無限に繰り返した後、$K_i$ 番目の文字は何かを求める。
たとえば `abc`だと以下のように、操作のたび文字列が後ろに伸びていきます。
文字列の長さが操作のたびに $2$ 倍になっていく ··· $2$ 冪の香りがします。
```
abc
abcABC
abcABCABCabc
abcABCABCabcABCabcabcABC
```
まず、$K_i$ 番目の文字が元から反転してるかしてないは一旦忘れて、何になるかはオリジナルの文字列の $(K_i - 1) \mod N$ を見ればわかります。
あとはその文字が反転してるのか、してないのか。
そこまでを実装すると以下になります。
```haskell
main :: IO ()
main = do
s <- getLine
q <- getInt
ks <- getInts
let n = length s
let sa = listArray @UArray (0, n - 1) s
res =
[ bool c (toggleChar c) $ (反転する?)
| k <- ks,
let c = sa ! ((k - 1) `mod` n)
]
putStrLn $ addSpaces res
-- >>> toggleChar 'A'
-- 'a'
toggleChar c
| isLower c = toUpper c
| isUpper c = toLower c
| otherwise = error "Invalid"
addSpaces :: String -> String
addSpaces [] = []
addSpaces [x] = [x]
addSpaces (x : xs) = x : ' ' : addSpaces xs
```
この「反転するかしないか」の判定をどうするか?
$K_i$ が最大で $2 \times 10^5$ 個あり、操作回数がほぼ無限回なので $N$ や $K_i$ の値から $O(1)$ もしくは対数時間程度で判定できる必要がありそうです。
操作を分析してみます。
先の `abc` の例をもとに、先頭の `a` だけに着目してみます。
```
a
aA
aAAa
aAAaAaaA
```
こうなりますが、一番左の文字が `a, a, a, a` と `a` が続き、右端が `a, A, a, A` と交互に反転しているあたりが怪しい。
操作 $1$ 回を状態遷移と捉えて遷移図を書くと、綺麗な二分木が出来ました。
操作1回につき長さが常に $2$ 倍になっていくので、操作1回あたり木の高さが増えると考えると二分木になるのは当然といえば当然です。
![[IMG_2136.jpeg|800]]
ここまで来ると構造が見えてきて、
- 二分木の親から子へ向かうにあたり、左にいくときは反転しない、右にいくときは反転
- 左から $K_i - 1$ 番目の位置にある頂点に、根から辿り着くのに、何回右の辺を辿ったかで反転回数が分かる。それが奇数なら、最終結果は元の文字から反転
- 二分木と $10$ 進数の対応を考えると、木の左に $0$ で、木の右に $1$ を割り当てることにより経路をビット列で表現することができるのを利用できそう (これは知識)
ということが分かります。
`a` が出現する `0, 3, 6, 9, 12, 15, 18, 21 ...` という位置は $N$ で割ると `0, 1, 2, 3, 4, 5, 6, 7 ...` です。
これで $K_i - 1$ に対してこの二分木と $10$ 進数の対応がつき、二分木の右の辺を何回辿ったかは $K_i - 1$ のビットが立っている回数で分かります。つまり `popCount` が使えます。
二分木の経路とビット列の対応を予め知識として持っていなければ、もっと手こずったかもしれないです。
```haskell
main :: IO ()
main = do
s <- getLine
q <- getInt
ks <- getInts
let n = length s
sa = listArray @UArray (0, n - 1) s
res =
[ bool c (toggleChar c) $ odd parity
| k <- ks,
let c = sa ! ((k - 1) `mod` n)
parity = popCount $ (k - 1) `div` n
]
putStrLn $ addSpaces res
{-- snip. --}
```
## [E - 1D Bucket Tool](https://atcoder.jp/contests/abc380/tasks/abc380_e) (upsolve)
Union-Find を使いつつ、実装を頑張る問題でした。
考察は合っていたのですが、実装の正確性を欠き、時間内に正しく実装することができず。
クエリ毎に、同じ色になっている隣接要素がくっついていく、というところからまず Union-Find の匂いがします。同じ色になった隣接要素の繋がりをグラフの連結で表現します。
このときクエリ $1$ 回あたり、指定されたマス $x$ の連結成分の、左右隣の頂点にしか興味がない、というところがポイントです。
左右の頂点番号がわかれば、そこからその左右の代表元もわかります。
代表元の色が管理できていれば、隣のグループが同じ色なら連結するし、しないなら連結しない、という判断が可能です。
さらに、Union-Find なら、とある頂点が含まれる連結成分のサイズを高速に取得できるので、ここから操作によって何マスが色 $c$ に変わるか判定でき、各色今、何マスを使っているか更新可能になります。
というわけで
- Union-Find でマスの連結を管理
- 各連結成分の代表元の、左と右の頂点番号をそれぞれ管理
- 各代表元がその時点で何色かを管理
- さらに、各色が現在で何個あるかを管理
で合計 5 個のデータ構造を用意して、クエリに応じてシミュレーションしていきます。
Union-Find 以外は全て $N$ 個の頂点番号をインデックスにした可変配列になりますが、このインデックス値を常に代表元で参照するところがミソです。
AC して改めてみてみると、丁寧に実装していけばロジックそのものは難しくはない問題です。その点は D の方が難しかったかも。
一方、5個のデータ構造を更新していく実装を、残り時間が迫っているプレッシャーを感じながら正確にこなすのが厳しかったです。
サンプルは通るものの WA になる、というケースから抜け出せずゲームオーバーでした。
この手の可変配列をゴリゴリ書き換える問題では、Haskell だとその実装がやや複雑、というのも厄介でした 😓
```haskell
main :: IO ()
main = do
[n, q] <- getInts
qs <- replicateM q getInts
uf <- newUF @IOUArray (-1, n + 2) (-1)
left <- newListArray @IOUArray (0, n + 1) [-1 .. n]
right <- newListArray @IOUArray (0, n + 1) [1 .. n + 2]
counter <- newArray @IOUArray (0, n + 1) 1
color <- newListArray @IOUArray (0, n + 1) [0 .. n + 1]
for_ qs $ \case
[1, x, c] -> do
v <- rootUF uf x
originColor <- readArray color v
size <- getSizeUF uf v
modifyArray counter originColor (+ negate size)
modifyArray counter c (+ size)
l <- rootUF uf =<< readArray left v
r <- rootUF uf =<< readArray right v
-- 色更新
lc <- readArray color l
rc <- readArray color r
when (lc == c) $ unite uf l v
when (rc == c) $ unite uf v r
v' <- rootUF uf v
writeArray color v' c
-- 連結成分の左端、右端の位置更新
l' <- readArray left l
r' <- readArray right r
let (newL, newR) = case (lc == c, rc == c) of
(True, True) -> (l', r')
(True, False) -> (l', r)
(False, True) -> (l, r')
(False, False) -> (l, r)
writeArray left v' newL
writeArray right v' newR
--
[2, c] -> do
print =<< readArray counter c
_ -> error "Invalid"
```
## 感想など
水パフォ 3連続取ってからの、緑パフォでレートは $-4$
E を解いていれば水パフォ確定だったところ、実装の正確性を欠いて AC できなかったのはとても悔しい。
とはいえ、今回も焦らず各問題、じっくり考察しきってから実装に移ったことで、
誤った解法に固執して沼るみたいなことはなく、それは良かったです。
A 問題をソートで済ませればいいや、と冷静にやれたのもよかったです。
開始 15 分前まで仮眠していて、寝ぼけた頭で 21:00 を迎えたためかいつもの緊張がまったくなく、ほどよい感じでスタートを切れたのが良かったのかもしれません。