# ABC350 振り返り
- [AtCoder Beginner Contest 350（Promotion of AtCoderJobs） 告知 - AtCoder](https://atcoder.jp/posts/1221)
- ABCDE 5完 (1349) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc350)
![[スクリーンショット 2024-04-20 23.56.44.png]]
![[スクリーンショット 2024-04-20 23.58.18.png]]
ABC350 でした。
鬼門である E の期待値 DP を解いてパフォーマンス 1349 で上々でした。
- A ··· $S$ の末尾三文字を整数にして `inRange (1, 349) x && x /= 316` 判定。`x < 350` で判定すると `ABC000` の考慮漏れになる罠
- B ··· $\{1 \ldots N\}$ の集合からスタートして、シミュレーションして集合に残った元の数を数える
- C ··· 各 $A_i$ のインデックス位置を配列でもっておき $i = 1$ から順に「$1$ は位置 $3$ にあるから位置 $3$ にある値と交換」を繰り返す
- D ··· Union-Find。連結成分ごとの辺の数 $M$ を数えておき、連結成分ごとに $_NC_2 - M$ で、対象のペアの組数がわかる
- E ··· メモ化再帰で期待値DPする。各局面で $X$ 円払う操作、$Y$ 円払う操作両方を計算して小さいほうを採用。自己ループ除去あり
ここ数回負けが続いましたが、挽回できて良かったです (小学生並みの感想)
----
## [A - Past ABCs](https://atcoder.jp/contests/abc350/tasks/abc350_a)
入力に与えられた `ABC349` が実際に開催された ABC かどうか判定する。
例外は `ABC000` と `ABC316` は開催されていないこと。そして後者は問題文に明示的に書かれているし、テストケースもある。
しかし前者は問題文を良く読むと暗に書いているが見落としがち。
というわけで `ABC000` が考慮漏れで 2ペナもらいました 😇
1ペナ目はしょうがないとして、そこで「あれ、整数の変換方法間違えたかな」と思って適当に直して送信するという愚行をかまして 2ペナ。こういう適当な修正は単に +5分もらうだけなのに、懲りてない。
順位表みてるとお気に入りにいる人の半数ぐらいが1ペナもらってました。
運動会の 100m 走で、スタート直後に落とし穴が掘ってあってみんな落ちる、みたいな。
```haskell
main :: IO ()
main = do
s <- getLine
let xs = drop 3 s
x = read @Int xs
printYn $ inRange (1, 349) x && x /= 316
```
## [B - Dentist Aoki](https://atcoder.jp/contests/abc350/tasks/abc350_b)
$i$ 回目の歯の治療で $T_i$ を治療するが、トグルになっている。
つまり、$T_i$ がそのとき存在すれば取り除き、存在しなければ追加する。
というわけで $\{1 \ldots N\}$ の集合からスタートして、$i \ldots N$ まで $T_i$ に応じてシミュレーションし、結果集合に残った元の数を数えます。
```haskell
main :: IO ()
main = do
[n, q] <- getInts
ts <- getInts
let s' = foldl' f (IS.fromList [1 .. n]) ts
where
f s t
| IS.member t s = IS.delete t s
| otherwise = IS.insert t s
print $ IS.size s'
```
こういうあったら削除、なかったら追加という計算ときどきやるので、盆栽にしても良いかもしれない。
```haskell
main :: IO ()
main = do
[n, q] <- getInts
ts <- getInts
let s' = foldl' (flip deleteOrInsertIS) (IS.fromList [1 .. n]) ts
print $ IS.size s'
deleteOrInsertIS :: IS.Key -> IS.IntSet -> IS.IntSet
deleteOrInsertIS i s
| IS.member i s = IS.delete i s
| otherwise = IS.insert i s
```
## [C - Sort](https://atcoder.jp/contests/abc350/tasks/abc350_c)
$(1 \ldots N)$ の並び変えである数列が与えられる、これを $N - 1$ 回以内で、値をスワップすることでソートする。
そのときのスワップ過程を出力せよ、というもの。
$N$ 個の値が $(1 \ldots N)$ まで隙間なく並んでいる、という特殊ケースを利用すれば汎用的なソートの $O(N \log{N})$ よりも効率的なソートができまっせ、というのが暗に示されています。
$i = 1 \ldots N$ の順に、その時点で位置 $i$ にある $A_i$ と、$i$ が値として格納されている $A_j = i$ の位置 $j$ をスワップします。
入れ換えなくてよいものは $i = j$ なので、フィルタする。
実装的には数列 $A$ の入れ換えだけでなく、各値の位置を別途もっておきそちらもスワップします。
これは MArray で手続き的にやるほうがむしろ簡単と思い、IOUArray でやりました。
··· と涼しい顔で書いてますが、こういう配列の値と、索引を両方管理して swap してくみたいなのは実装中に頭がごちゃごちゃしてきてとてもつらい。
[ABC250 C - Adjacent Swaps](https://atcoder.jp/contests/abc250/tasks/abc250_c) という類題があるのですが、この問題が AtCoder Daily Training で出るたびに頭が沸騰するので、今回も紙に方針を丁寧にまとめてから実装しました。それでもなお、頭がごちゃつきました。
この問題で苦戦して、ペースを崩した方も多かったようです。こわい。
```haskell
main :: IO ()
main = do
n <- getInt
as_ <- getInts
as <- newListArray @IOUArray (1, n) as_
ix <- newArray @IOUArray (1, n) (-1 :: Int)
for_ (zip as_ [1 :: Int ..]) $ \(a, i) -> do
writeArray ix a i
res <- for [1 .. n] $ \a -> do
x <- readArray as a
i <- readArray ix a
j <- readArray ix x
swapArray as i j
swapArray ix j x
return (j, i)
let res' = [(i, j) | (i, j) <- res, i /= j]
print $ length res'
for_ res' printTuple
```
## [D - New Friends](https://atcoder.jp/contests/abc350/tasks/abc350_d)
Union-Find 案件。
友達の友達を友達にできるとき、あと何組新しい友達関係を作ることができるか?
グラフを手で書いてみるとすぐにわかりますが、同一の連結成分の中で、まだ辺で結ばれていない頂点同士を、辺で結べる回数が答えです。
直接、辺で結べる回数を求めようとすると少し大変かもしれない。
頂点数 $N$、辺の数$M$ の連結成分における、2頂点の組み合わせは $_NC_2$
うち、すでに結ばれている組み合わせは $M$ 個
なので連結成分ごとに $_NC_2 - M$ すれば OK です。
この辺の、$_nC_2$ から辺の数を引くことで、まだペアになってない組み合わせの個数をみつけるというのは [ABC282 D - Make Bipartite 2](https://atcoder.jp/contests/abc282/tasks/abc282_d) でやったことがあります。グラフを手で書いてるうちに想起されました。
もとい、連結成分ごとに、ある連結成分に辺が何本あるかを求めたいわけですがこれは Union-Find で計算できます。
盆栽の Union-Find にその機能を持たせていたので、簡単でした。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getTuple
uf <- newListUF @IOUArray (1, n) (-1) uvs
cs <- getComponentsUF uf
res <- for cs $ \vs -> do
x <- getEdgeSizeUF uf (head vs)
return $ nc2 (length vs) - x
print $ sum res
```
## [E - Toward 0](https://atcoder.jp/contests/abc350/tasks/abc350_e)
メモ化再帰で期待値DP する問題です。自己ループ除去も必要です。
[ABC300 E - Dice Product 3](https://atcoder.jp/contests/abc300/tasks/abc300_e) に良く似ていますが、そこにもう少し捻りが入っています。
ある局面で取れる行動は、$X$ 円を払う行動、$Y$ 円を払う行動の二種類あります。
$X$ 円払う場合は確実に $N$ を $N / A$ できる。一方 $Y$ 円を払う場合はサイコロの目 $b$ に応じて $N/ b$ になる。
その都度最適な行動をして、$N = 0$ を目指すとき、支払うコストの期待値を最小化したい。
よく考えてみると $N$ がある値のとき、どちらの行動をとるとよいかは、
その局面からの期待値の増加分が小さい方を選べばいいだけなので両方計算すればよいです。難しくないです。
というわけで、期待値 DP を解いていきます。
期待値DPはまず、期待値が $0$ になる局面がどこなのかをはっきりさせる必要があります。
(そして、ここをよく間違えます)
今回の問題では $N = 0$ のとき、それ以上操作をする必要がないわけですから、支払うコストの期待値が $0$ になります。
よって $dp(0) = 0$ です。この $dp(0) = 0$ を足場に部分問題を少しずつ解いていって、 $dp(N)$ を求めることになります。
一方、この問題は $N \leq 10^{18}$ と大きいので、配列を使って $0 → N$ に向かう計算をしていく DP は難しいでしょう。
ではどうするか。
$N$ の割り算に使われる分母は $1 \ldots 6$ と種類が少ないので、$N$ から割り算をどんどんやっていくと
出現する値は飛び飛びになって $10^{18}$ よりずっと少ない、かつ重複しまくることがわかります。
メモ化再帰で、再帰によって DFS 的に $dp(0) = 0$ に辿り着いて、そこから値が $N$ に向かって確定していく方式で解くと良いです。
メモ化再帰にあたり、注意すべきは $Y$ 円の行動をとったがサイコロの目が $1$ になるときです。
この場合 $dp(n) → dp(n)$ という遷移が生まれてしまうので無限ループになります。
期待値DPにおける、自己ループ除去という典型ですね。
この自己ループ除去は
$\displaystyle dp(n) = \frac{1}{6} \times (Y + dp(\frac{n}{1}) + Y + dp(\frac{n}{2}) + \ldots + Y +dp(\frac{n}{6}))$
という DP の遷移式を変形してやってもよいのですが (その方法は公式解説にあります)、
ABC300 の解説動画ですぬけさんが「確率 $1/5$ のサイコロと考えれば良い」といってたのを思い出しました。
確率は $1/5$ になるが、追加コストの総量は $+5Y$ にならず $+6Y$ のまま...と計算すると辻褄が合います。
Haskell でのメモ化再帰は、State モナドを使って Map に値をメモ化する、という方法でいつも実装しています。
計算がモナディックになってやや沼るので、練習が必要ですね。
```haskell
dp _ _ _ 0 = return 0
dp a x y n = do
memo <- gets (IM.lookup n)
case memo of
Just val -> return val
Nothing -> do
costX <- do
k <- dp a x y (n `div` a)
return $ fromIntegral x + k
ys <-
traverse
( \b -> do
k <- dp a x y (n `div` b)
return $ fromIntegral y + k
)
[2 .. 6]
let costY = (fromIntegral y + sum ys) / 5
val = min costX costY
modify (IM.insert n val)
return val
main :: IO ()
main = do
[n, a, x, y] <- getInts
let v = evalState (dp a x y n) IM.empty
print v
```
## 感想など
こうして振り返ってみると、比較的最近の類題が多い回だったなと思います。
ABC の過去問を繰り返し解くという方法で精進してる自分にとっては、相性がよかった回かも知れません。
このところは相変わらずバチャで精進をしていますが
- AtCoder Daily Training は Medium を卒業して Hard を中心にやる
- ABC300 〜 ABC349 までやる (全部終わった)
という風に進めてます。
ADT Medium は、だんたん問題を記憶で解いているだけになって負荷が足りなくなってきたので Hard に切り替えました。
Hard だと解けない問題も多いのですが、upsolve できそうなものはする、というのを根気よくやってます。
ABC の過去問は、やってみるとこれはこれで発見があって面白いですね。
解法も覚えてるし解けるでしょ、と思っていた問題が解けないという思い込みみたいなものもちょいちょいありよく鼻を折られています😅
あるいは、実装力が上がったことで、過去に苦労した問題があっさり解けるということも多いです。
しばらくはこの方式で続けてみようと思います。