# ABC392 振り返り
- [日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392） - AtCoder](https://atcoder.jp/contests/abc392)
- ABCD 4完 (1083) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc392)
![[スクリーンショット 2025-02-09 8.46.04.png]]
- A (灰, 11) ··· 順列全探索
- B (灰, 29) ··· Set 系の `difference` を使うと楽
- C (灰, 132) ··· 人の関係を有向グラフにし、人 → ゼッケン、ゼッケン → 人を引けるように配列を二つ用意
- D (茶, 579) ··· おちついて確率を計算する。全探索で OK
- E (水, 1218, upsolve) ··· Union-Find で冗長な辺を割り出す。連結成分が $k$ 個あったら $k - 1$ 個の冗長辺を使ってそれらを結ぶ
- F (水, 1395, upsolve) ··· `Data.Sequence`の `insertAt` で瞬殺
でした。
E の冗長辺を結ぶ処理で WA が一つでてしまい、それを取るのに必死になって F をほとんどみないままゲームオーバー
F はよくみたら Haskell だとスーパー Easy な問題で、もったいなかったです
## [A - Shuffled Equation](https://atcoder.jp/contests/abc392/tasks/abc392_a)
3変数なので全パターンを列挙してもいいですが `permutations` を使うのが楽
```haskell
main :: IO ()
main = do
as <- getInts
let res = [b1 * b2 == b3 | [b1, b2, b3] <- permutations as]
printYn $ or res
```
## [B - Who is Missing?](https://atcoder.jp/contests/abc392/tasks/abc392_b)
$1 \ldots N$ に含まれない数を出す、というのは Set 系の `difference` を使うと簡単。欠けた数字を割り出すのによく使うイディオムです。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
let diff = IS.difference (IS.fromList [1 .. n]) (IS.fromList as)
print $ IS.size diff
printList $ IS.toList diff
```
## [C - Bib](https://atcoder.jp/contests/abc392/tasks/abc392_c)
問題文を読み解くのが面倒な問題。
人の関係は有向グラフで結ばれているグラフ (Functional Graph) として表現すると楽
あとはゼッケンの番号を割り出す方法が欲しい。人 → ゼッケン、ゼッケン → 人の両方の検索が必要なので配列を正方向、逆方向で用意してあとは問題文通りに実装。
```haskell
main :: IO ()
main = do
n <- getInt
ps <- getInts
qs <- getInts
let qa = listArray @UArray (1, n) qs
invQ = array @UArray (1, n) $ zip qs [1 :: Int ..]
g = graph (1, n) $ indexed 1 ps
res = [qa ! y | i <- [1 .. n], let x = invQ ! i, let y = head $ g ! x]
printList res
```
## [D - Doubles](https://atcoder.jp/contests/abc392/tasks/abc392_d)
例えば $(1, 2, 3)$ というサイコロと、$(1, 2, 2, 1)$ というサイコロがあったとすると
- 出目 $1$ が被る確率 ··· 一つ目のサイコロで $1$ が出る確率は $\frac{1}{3}$ 、二つ目では $\frac{2}{4}$、 この二つが同時に出現する確率なので積で結び $\frac{1}{3} \times \frac{2}{4} = \frac{2}{12}$
- 出目 $2$ が被る確率 ··· 同様に計算して $\frac{1}{12}$
- 出目 $3$ は一方にしかないので出ない ··· 確率 $0$
となり、出目 $1$ と出目 $2$ の出現はそれぞれ独立なので和で結合し $\frac{2}{12} + \frac{2}{12} = \frac{4}{12} = \frac{1}{3}$
と計算できます。
必要な部品としては
- 2 つのサイコロを比較するにあたり、それぞれのサイコロの出目の出現頻度
- 2 つのサイコロを比較するにあたり、両方に存在する出目のリスト (一方にしかない出目は計算対象にしなくていい)
です。前者はバケットをとり、後者は集合の `intersection` を使えばよいでしょう。
というわけで、各サイコロをバケットと 集合に変換しておき、`combintations 2` で全ての組み合わせを全探索し先の容量で確率を計算する。
$N \leq 100$ なので `combinations 2` は高々 $4950$ 通り、サイコロの出目の長さは全体を足しても $10^5$ 程度なので割と愚直でもいけます。
```haskell
main :: IO ()
main = do
n <- getInt
items <- replicateM n $ do
k : as <- getInts
return (k, as)
let items' =
[ (k, bucket, s)
| (k, as) <- items,
let bucket = toBucket (1, 10 ^ 5) as
s = IS.fromList as
]
res =
[ sum' [(fromIntegral (bucket1 ! i) / fromIntegral k1) * (fromIntegral (bucket2 ! i) / fromIntegral k2) | i <- IS.toList s]
| ((k1, bucket1, s1), (k2, bucket2, s2)) <- comb2 items',
let s = IS.intersection s1 s2
]
print $ maximum res
```
## [E - Cables and Servers](https://atcoder.jp/contests/abc392/tasks/abc392_e) (upsolve)
Union-Find で、空のグラフを用意しそこに辺を継ぎ足していく。ある辺を加えるとき、その両端が既に連結している場合はそれを冗長な辺と判断し、脇に寄せておく。
これで余りの辺がわかる。
ところで、グラフ全体を連結にするには先の Union-Find で出来上がった連結成分同士を繋げればよい。
できあがった連結成分の数を $k$ とすると、冗長な辺を $k - 1$ 本繋ぎ直すことでグラフ全体を連結にすることができる。
つまり、最小の操作回数は必ず $k - 1$ になる。
冗長な辺からどれでもいいので $k - 1$ 本をチョイスし、それをまだ連結できてない別の連結成分の代表元に繋ぎなおす。
これでいけます。
繋ぎ直しの処理をどうするかですが、$k - 1$ 本の辺のリストと代表元のリストを同時に再帰で回し、辺の一端 $u$ と代表元 $r$ がまだ連結してなければその二者を連結する。
もし連結している場合は、辺は消費せずに $r$ を代表元リストの一番後ろに回して次の代表元をみる。
この再帰でかならず $k - 1$ 本は消費されるはずなので、辺のリストが空になるまで、やる。
本番ではこの繋ぎ直しの処理の記述を微妙に間違えていて、 WA 1 個が取れず結局時間オーバーになってしまいました。無念
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getTuple
uf <- newUF @IOUArray (1, n) (-1)
edges <- for (indexed 1 uvs) $ \(i, (u, v)) -> do
same <- isSame uf u v
if same
then do
return $ Just (u, i)
else do
unite uf u v
return Nothing
vss <- getComponentsUF uf
roots <- for vss $ \vs -> do
rootUF uf (head vs)
let k = length roots
result <- loop uf (take (k - 1) $ catMaybes edges) roots []
print (k - 1)
for_ result $ \(i, u, v) -> do
printList [i, u, v]
loop _ [] _ acc = return acc
loop _ _ [] acc = return acc
loop uf ((e@(u, i) : es)) (r : rs) acc = do
same <- isSame uf u r
if not same
then do
unite uf u r
loop uf es rs ((i, u, r) : acc)
else loop uf (e : es) (rs `snoc` r) acc
```
## [F - Insert](https://atcoder.jp/contests/abc392/tasks/abc392_f) (upsolve)
並び順を保証されているデータ列の任意の位置に数を追加していく。
初期状態でデータ列は空とみなすことができ、挿入回数は $O(10^5)$ 程度。
Haskell なら Data.Sequence に `insertAt` という位置指定でシーケンスに値を挿入できる API があり、計算量は挿入位置が $i$ でデータサイズが $n$ のとき $𝑂(log(min(𝑖,𝑛−𝑖)))$ 程度です。なので、これを使うだけで解ける。
E の WA 1 個をとるのに執着してしまい、F がまさかこんな瞬殺問題だとは思わず。もったいない!
Data.Sequence がない場合は双方向リストとか、セグ木や BIT を使って解けばよさそうです。
```haskell
main :: IO ()
main = do
_ <- getInt
ps <- getInts
let q' = foldl' f Seq.empty (indexed 1 ps)
where
f q (i, p) = Seq.insertAt (p - 1) i q
printList $ toList q'
```