# ABC383 振り返り
- [大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383） - AtCoder](https://atcoder.jp/contests/abc383)
- ABCDE 5完 (1524) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc383)
![[スクリーンショット 2024-12-08 10.39.58.png]]
ABC383 でした。
青diff の E を解いてパフォーマンス 1524 と上々でした。
- A (灰) ··· 一つ前の時刻からの経過分と同じだけ水が減るのを考慮しながら、$V_i$ を加算する
- B (灰) ··· `.` のマスを 2 つ選ぶ組み合わせを全探索
- C (茶) ··· 多始点 BFS
- D (緑) ··· 約数 $9$ 個は $N$ を素数 $p, q$ で $N = p^8$ か $N = p{^2}q{^2}$ と表現できるとき。その数を数え上げる
- E (青) ··· 最小全域木を構築しながら、その時点で数列 $A$ と数列 $B$ に含まれる頂点でペアにできる数を数える
でした。
## [A - Humidifier 1](https://atcoder.jp/contests/abc383/tasks/abc383_a)
A 問題にしては難しい。普段なら B 問題で出そうな問題です。
前回水を注いだ時点から次に水を注ぐ時点までの経過時間分、水が減る。
ので、$V_i$ を累積していきつつその時点の累積値 $acc$ から減衰分を引く、ということをやって畳み込みます。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- replicateM n getTuple
let ans = foldl' f 0 (zip ((0, 0) : xs) xs)
where
f acc ((prevT, _), (ti, vi)) = max 0 (acc - (ti - prevT)) + vi
print ans
```
## [B - Humidifier 2](https://atcoder.jp/contests/abc383/tasks/abc383_b)
グリッドが $10 \times 10$ 程度と狭いので、スタート位置の $2$ 点の組み合わせを全部試す、でよいです。
二つのスタート地点それぞれからマンハッタン距離 $D$ 以下かつ `.` のマスの座標を列挙。そのユニーク数が答え。
最初、マンハッタン距離 $D 以下$ のマスを列挙するのに `sequence [[0 .. d], [0 .. d]]` と書いていて答えが合わず頭を抱えました。正しくは `[-d ..d]` という凡ミス。
10 分程度ロスしてしまいました。print デバッグしてなんとか回避。
こういう凡ミスが、案外みつけるのに時間がかかります 😓
```haskell
distance :: (Num a) => (a, a) -> (a, a) -> a
distance (x1, y1) (x2, y2) = abs (x1 - x2) + abs (y1 - y2)
main :: IO ()
main = do
[h, w, d] <- getInts
grid <- getCharGrid ((1, 1), (h, w))
let resolve v =
[ u
| [dx, dy] <- sequence [[-d .. d], [-d .. d]],
let u = v + (dx, dy),
distance v u <= d,
grid !? u == Just '.'
]
let res = [nubOrd (resolve a ++ resolve b) | (a, b) <- comb2 (findArrayIndices (== '.') grid)]
print $ maximum (map length res)
```
## [C - Humidifier 3](https://atcoder.jp/contests/abc383/tasks/abc383_c)
`H` の箇所から距離 $D$ 以下の移動で辿りつけるマスの数を列挙する。
これはもう、複数ある `H` の箇所から一斉スタートする多始点 BFS です。
「多始点 BFS 」というと特別な感じがしますが、実際は BFS の初期状態を `H` のマスを距離 $0$ に初期化してからスタートするだけ。
BFS を盆栽する場合、複数の開始点とその初期距離を設定できるインタフェースにしておくと良いです。
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)]
main :: IO ()
main = do
[h, w, d] <- getInts
grid <- getCharGrid ((1, 1), (h, w))
let v0s = findArrayIndices (== 'H') grid
dist = bfsWithBuffer f (-1) (bounds grid) [(v0, 0) | v0 <- v0s]
where
f v = [u | di <- lrud, let u = v + di, inRange (bounds grid) u, grid ! u /= '#']
res = [x | x <- elems dist, inRange (0, d) x]
print $ length res
```
## [D - 9 Divisors](https://atcoder.jp/contests/abc383/tasks/abc383_d)
$N$ 以下の正整数のうち、正の約数をちょうど $9$ 個もつものの個数を数える。$N \leq 4 \times 10^{12}$ あるので、全探索は難しい。
高校数学の問題ですね。約数の個数は素因数分解して得られる素数の指数から求められます。
たとえば
$180 = 2^2 \times 3^2 \times 5$
ですが、各素数の指数に $+1$ して積を取ると約数の個数になる。ので $180$ の約数は $3 \times 3 \times 2 = 18$ 個です。
その素数を使わないケースが指数 $0$ で、あとは積の法則でそこにある素数の組み合わせ数。なので各素数の指数に $0$ 一個分 $+1$ して積、です。
ここから考えると約数 $9$ 個というのは $9 = (2 + 1) \times (2 + 1)$ もしくは $9 = (8 + 1)$ なので、$p^2q^2$ もしくは $p^8$ で表現できる数です。
これを数えます。
$p^8$ の方は簡単。$N$ 以下となると $p$ はあまり大きくならないので、適当な数までエラトステネスの篩で素数を求めて $p ^ 8 \leq N$ なものを残せば良い。
$n = p^2q^2$ は $p \times q = \sqrt n$ とも言えるので $1 \ldots \sqrt N$ まで $p$ を固定して $p \times q = \sqrt N$ になれる $q$ を数える。
本番ではここを二分探索で求めましたが、$1 \dots \sqrt N$ までを素因数分解して $p \times q$ の形になってるものを残す、の方が簡単でした。
```haskell
main :: IO ()
main = do
n <- getInt
let ps1 = primes (10 ^ 5)
res1 = [p | p <- ps1, fromIntegral p ^ 8 <= fromIntegral n]
let mf = minFactorSieve (isqrt n) -- osa_k法
res2 =
[ case factorize mf x of
[a, b] | a /= b -> 1 :: Int
_ -> 0
| x <- [1 .. isqrt n]
]
print $ length res1 + sum' res2
```
## [E - Sum of Max Matching](https://atcoder.jp/contests/abc383/tasks/abc383_e)
最小全域木を構成しながら、その時点で作ることができるペアの数を数えることで、解けます。
$f(x, y)$ を頂点 $x$ と頂点 $y$ のパスに含まれる重みの最小値、ですがここでパスは最短経路ではないというところがポイントです。
サンプル $2$ の例がヒントになってました。
![[IMG_2244_1.jpg|400]]
使わない辺がある。その辺は重みが大きい。たしかに考えてみれば、全頂点を結んでいる辺の重みが小さければ小さいほど良く、全域木にさえなっていればすべての頂点間で行き来ができる。
ということから、最小全域木だな〜と閃きます💡
クラスカル法で最小全域木を構築しながら貪欲に何かをやる、というのは時折見かける典型で、それでうまくいきそう。
あとはその「何か」ですが、ある時点の全域木を考えると例えば以下のようになります。
![[IMG_2244_2.jpg|600]]
この問題では $A_i$ と $B_i$ は一対一対応になるのと、グラフは常に木になっていることを考えると、この連結成分からは $A_i$ と $B_i$ のペアを $min (A_i の個数, B_i個数)$ だけ作ることができると言えます。
また、クラスカル法の性質上から常にその時点での部分木の総コストは最小ですから、そこで作ることができる $x, y$ ペアの $f(x, y)$ は最適になっているはず。
Union-Find で連結成分ごと (代表元に) に、その時点でその連結成分に含まれる $(A の個数, B の個数)$ を持っておけばペア数を求められます。
辺 $(u, v)$ を追加する際、$u$ 側の個数、$v$ 側の個数を求めて、また併合後にそれがどう変化するかも求める。これで、$(u, v)$ を追加したときに増えるペア数がわかるので、
そこに $w_i$ を掛ければ辺 $(u, v)$ を追加することによる寄与数が求まる。主客転倒です。
```haskell
main :: IO ()
main = do
[n, m, k] <- getInts
uvs <- replicateM m getWeightedEdge
as <- getInts
bs <- getInts
let uvs' = sortOn snd uvs
uf <- newUF @IOUArray (1, n) (-1)
let bucketA = toBucket (1, n) as
bucketB = toBucket (1, n) bs
counter <- newListArray @IOArray (1, n) $ zip (elems bucketA) (elems bucketB)
acc <- newIORef (0 :: Int)
for_ uvs' $ \((u, v), w) -> do
ru <- rootUF uf u
rv <- rootUF uf v
when (ru /= rv) $ do
(au, bu) <- readArray counter ru
(av, bv) <- readArray counter rv
let before = min au bu + min av bv
ax = au + av
bx = bu + bv
after = min ax bx
diff = after - before
modifyIORef' acc (+ diff * w)
unite uf u v
r <- rootUF uf u
writeArray counter r (ax, bx)
print =<< readIORef acc
```
## 感想など
B の実装、というか凡ミス探しでちょっともたついてしまい、やばいかな〜と思いましたが C が多始点 BFS 貼るだけだったので、挽回できました。
D を解いた時点で E がまだあまり解かれていなかったので、これはまあ、D ぐらいまで解いておけば冷えることもなかろう、と思って落ち着いて E の考察ができました。
前回の反省を活かして、E と F 両方問題をある程度理解してから、最小全域木っぽい E と、DP の F どっちがいけるか? E の方が方針は見えているので E にいきました。
サンプル2 まで絵を描いてみたのが、結果的に最小全域木に気づくきっかけになり、よかったと思います。
レートは 1181 となり、いよいよ水色に近づいてきました。
次回も勝って、年内に入水、そんでもってアドベントカレンダーに入水記事 ···と行きたいところですが油断は大敵です。
引き続きがんばります。