# ABC399 振り返り
- [AtCoder Beginner Contest 399 - AtCoder](https://atcoder.jp/contests/abc399)
- ABCD 4完 (1421) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc399)
![[スクリーンショット 2025-03-31 10.20.30.png]]
ABC399 でした。E が思いの他難しく1時間近くかけても解けず、4完に終わりました。
E はおそらく難易度的には青後半 〜 黃色ぐらいあり、自分と同レート帯の人はみな苦戦した様子。結果、パフォーマンスは 1421 と良かったです。
- A (灰) ··· `zipWith (==) s t` で同じ位置にある文字を比較する
- B (灰) ··· ソートしたのち、同じ得点をグルーピングしグルーピング長を数える
- C (灰 or 茶) ··· Union-Find でグラフを構築しながら、それを追加したら閉路になる辺の数を数える
- D (緑) ··· ある $A_i$ の登場位置ペア $(i, j)$ を考える。ある $i$ から見て隣、すなわち $i' = i + 1$ とペアの $j'$ と、$j$ が隣り合っていれば有効なペア、と数えていく
## [A - Hamming Distance](https://atcoder.jp/contests/abc399/tasks/abc399_a)
ハミング距離。$S$ と $T$ 二つの文字の同じ位置の文字を比較して異なるものの数を数えます。
```haskell
main :: IO ()
main = do
_ <- getInt
s <- getLine
t <- getLine
let res = zipWith (==) s t
print $ countBy (== False) res
```
## [B - Ranking with Ties](https://atcoder.jp/contests/abc399/tasks/abc399_b)
`3 12 9 9` という入力をソートして `12 9 9 3` にしてから、`[[12], [9, 9], [3]]` と同じ値のものをグルーピングすると、後続の計算が楽です。
Haskell なら `group` を使えばグルーピングは簡単です。
その上でできあがった各グループのグループ長を足し込んで行けば答えが求まります。
```haskell
main :: IO ()
main = do
n <- getInt
ps <- getInts
let ps' = groupOn snd . sortOn (Down . snd) $ indexed 1 ps
(_, res) = mapAccumL f 1 ps'
where
f r vs = (r + length vs, [(i, r) | (i, _) <- vs])
result = array @UArray (1, n) $ concat res
for_ [1 .. n] $ \i -> do
print $ result ! i
```
## [C - Make it Forest](https://atcoder.jp/contests/abc399/tasks/abc399_c)
350 点問題で身構えましたが、THE 典型問題でした。
Union-Find でグラフを構築しながら、その辺を加えると閉路ができるよ、という辺の数を数え上げると良いです。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getTuple
uf <- newUF @IOUArray (1, n) (-1)
acc <- newIORef (0 :: Int)
for_ uvs $ \(u, v) -> do
same <- isSame uf u v
if same
then modifyIORef' acc succ
else unite uf u v
print =<< readIORef acc
```
## [D - Switch Seats](https://atcoder.jp/contests/abc399/tasks/abc399_d)
`1 2 3 3 1 2` と入力があったとき、`1` に着目すると、最初に登場する `1` の隣は `2` です。そして遠く離れたところに出てくる `1` の隣もまた `2` です。
こういうペアが幾つあるかを数えていきます。
各数字 $A_i$ は二つずつ出てきますが、それらの位置が重要なので、$A_i$ が登場する位置 $(i, j)$ のペアを求めます。
ここで $i + 1 == j$ なもの、つまり最初から隣がカップルになっているものは邪魔なので取り除きます。(これがあるとコーナーケースに引っかかると思います)
その上で、$i$ を固定しながら $i$ の位置の右隣 $i' = i + 1$ を考えます。$i$ とペアになる $j$ と $i'$ とペアになる $j'$ を比較します。
このとき $j$ と $j'$ が (左右どちらでもいいので) 隣り合っていれば、$i$ の隣と $j$ の隣が同じ組みあわせなので、そのペアは有効なペアとして数え上げます。
これが基本的な考え方。
実装では、探索を楽にするために辞書 `IntMap` を使いました。
ある $A_i$ は必ず二つしか出てこない、よってその出現位置 $(i, j)$ をペアにして考察する··· というところが良い戦略だったと思います。
```haskell
main :: IO ()
main = do
t <- getInt
replicateM_ t $ do
_ <- getInt
as <- getInts
let pos = IM.map sort' $ imGraph (zip as [1 :: Int ..])
pos' = IM.fromList [(i, j) | (_, [i, j]) <- IM.toList pos, j /= i + 1]
res =
[ v
| (i, j) <- IM.toList pos',
let v = case IM.lookup (i + 1) pos' of
Just j' | abs (j - j') == 1 -> 1 :: Int
_ -> 0
]
print $ sum' res
```
ただし `IntMap` は遅く 1sec 近くかかるので、Array を使うようにしてもよいですね。こちらなら 300ms 程度でした。
```haskell
main :: IO ()
main = do
t <- getInt
replicateM_ t $ do
n <- getInt
as <- getInts
let ix = amap sort' $ accumArray @Array (flip (:)) [] (1, n) $ zip as [1 :: Int ..]
ix' = accumArray @UArray (flip const) minBound (1, 2 * n) [(i, j) | (_, [i, j]) <- assocs ix, j /= i + 1]
res =
[ v
| (i, j) <- assocs ix',
let v = case ix' !? (i + 1) of
Just j' | abs (j - j') == 1 -> 1 :: Int
_ -> 0
]
print $ sum' res
```