# ABC382 振り返り
- [AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382） - AtCoder](https://atcoder.jp/contests/abc382)
- ABCD 4完 (1056) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc382)
![[スクリーンショット 2024-12-01 11.23.37.png]]
こんにちは、Haskell で競技プログラミングをやっている CTO です。
ABC382 でした。
- A (灰) ··· `.` の数を数えて $+ D$ する
- B (灰) ··· `mapAccumR` で後ろから $D$ 個 `@` を `.` にする
- C (茶) ··· $B$ をソートして先頭から見ていき、ある $B_j$ を食べられる $A_i$ のうち最小の $i$ を決めていく。$B_j$ に対して条件を満たす $A$ は順序付き集合で探索。
- D (茶) ··· 樹形図を書いて、その通りに DFS で生成する
- E (青, upsolve) ··· 先にパックを開いた時レアを $x$ 枚引く確率を求める。その上で期待値DP だが自己ループ除去が必要
- F (水, upsolve) ··· 下にあるブロックから順番に、遅延伝搬セグメント木で $[l, r)$ 区間の高さを確定させていく。類題あり
C にすこし手間取ってしまったものの、D をさっと解いて挽回。
このまま E も〜 と行きたいところでしたが、自己ループ除去のところで詰まってしまいゲームオーバー。
結果的には E ではなく F に着手するべきでしたが後の祭りでした。惜敗。
## [A - Daily Cookie](https://atcoder.jp/contests/abc382/tasks/abc382_a)
問題文の読み取りに、普段の A 問題より少し時間を要しました。
$i$ 番目の文字が `.` なのか `@` なのかはどうでもよく、単に空箱が何個あるかがわかれば OK
$1$ 日 $1$ 枚クッキーを食べる、かつ $D$ 日分のクッキーは必ずあることが保証されているので $D$ に空箱の数を足したものが答え。
```haskell
main :: IO ()
main = do
[n, d] <- getInts
s <- getLine
let x = countBy (== '.') s
print $ x + dそ
```
## [B - Daily Cookie 2](https://atcoder.jp/contests/abc382/tasks/abc382_b)
A問題と問題の舞台は同じだが、今度は文字列の並び順に意味がある。
後ろから `@` のあるところを $D$ 個 `.` にする。
できればアキュムレータを使わないで書きたかったのですが、ぱっと思いつかず。`mapAccumR` でやりました。
```haskell
main :: IO ()
main = do
[n, d] <- getInts
s <- getLine
let (_, s') = mapAccumR f d s
where
f 0 c = (0, c)
f acc '.' = (acc, '.')
f acc '@' = (acc - 1, '.')
putStrLn s'
```
## [C - Kaiten Sushi](https://atcoder.jp/contests/abc382/tasks/abc382_c)
考察に時間を要しました。はやい人はこれを 5 分程度で解いていて、びびります。
この問題のポイントとしては「より先頭に近い位置にいる人が、ある一定の美味しさ以上の寿司は全部食べる」というところです。
例えば $A_1 = 3$ の人がいて、$B = (1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6)$ とあったら、美味しさ $3$ 以上の $B_i$ 、つまり $3$ 以降は全部 $A_1$ の人が食べます。
$A_2 = 1$ の人がいても、関係ありません。
先に挙げた例の通り、$B$ がソートされていると、ある $A_i$ に対し、ある一定の $B_j$ 以降は全部食べられるという構造があるため、ソートが鍵を握りそうです。
そこで、自分は美味しさが小さなものから考えていく··· $B$ を昇順にソートしてみていくことにしました。
$A_i$ を、$i$ と共に $(A_i, i)$ というタプルで集合 (Set) に入れておきます。
この集合は「まだ自分が食べられる寿司が回ってきてない人たち」の集合です。
この集合から新たに回ってきた $B_j$ を食べられる複数人を探索し、その中で最も先頭に並んでいる人を明らかにしていきます。
まず ソート済みの $B$ を先頭から見ていきながら、その $B_j$ を食べることができる人を全部、集合から取り出します。
取り出された人たちのうち、より先頭に並んでる人、つまり $i$ が最も小さい人がその $B_j$ を食べる人です。取り出された人たちのインデックス番号の minimum を取れば、それが確定します。
このとき $B$ は昇順に並んでいるので、集合から取り出された人たちは、つづく $B_{j + 1}$ 以降もすべて食べることができる人たちです。
もう「まだ自分が食べられる寿司が回ってきてない人たち」への所属条件は満たさないことになります。というわけで、集合から削除します。
Set ならこの集合から取り出して削除する計算は一件あたり $O(\log n)$ です。
これを繰り返して「$B_j$ を食べられる人のうち最も小さい $i$」を状態として更新していくと、答えが求まります。
何度も $O(n)$ の `minimum` を使うことになりますが、計算全体で $N$ 件走査するだけなので問題ありません。
Haskell だと集合から $x$ 以下の値すべて取り出して削除して、みたいな計算の実装含めて、ちょっと手間がかかりました。
```haskell
deleteLEViewSet x s0 = loop s0 []
where
loop s acc = case Set.lookupLE x s of
Just v -> do
let s' = Set.delete v s
loop s' (v : acc)
Nothing -> (acc, s)
main :: IO ()
main = do
[_, m] <- getInts
as <- getInts
bs <- getInts
let as' = zip as [1 :: Int ..]
s0 = Set.fromList as'
bs' = sort' (zip bs [1 :: Int ..])
result <- newArray @IOUArray (1, m) (-1 :: Int)
foldForM_ (s0, maxBound) bs' $ \(s1, idx) (bi, i) -> do
let (xs, s1') = deleteLEViewSet (bi, maxBound) s1
idx' = minimum (idx : map snd xs)
writeArray result i idx'
return (s1', idx')
for_ [1 .. m] $ \i -> do
ans <- readArray result i
print $ if ans == maxBound then (-1 :: Int) else ans
```
## [D - Keep Distance](https://atcoder.jp/contests/abc382/tasks/abc382_d)
結論ナイーブな DFS で解きます。$N \leq 12$ あたりから、ナイーブにやって問題ないだろ、と適当に判断しました。
樹形図を先に書くと分かりやすいですね。
![[IMG_2224.jpeg|450]]
こんな感じの樹形図になっていて、樹形図の生成といえば DFS です。
木の高さ、つまり数列の長さが $N$ になるまで再帰します。
例えば現在が $(1, 11)$ まで生成したところだとすると、そこから $(1, 11, 21), \ldots, (1, 11, 23)$ を生成するよう再帰を行います。
これを $(1, 11, p) \ldots (1, 11, q)$ とすると
- $p$ はその時点の列の末尾 $11$ に $+10$ したもの
- $q$ はその時点の列の長さ $+1$ を $k$ としたとき $M - 10 \times (N - k)$
で決まります。
Haskell だとこの手の樹形図的な DFS は記述パターンがあり、リストモナドを使うと書きやすいです。
do 記法と `a <- [p .. q]` で、リストコンテキストにして、再帰していけば OK
```haskell
main :: IO ()
main = do
[n, m] <- getInts
let xss = resolve n m []
x = length xss
print x
for_ xss printList
resolve :: Int -> Int -> [Int] -> [[Int]]
resolve n m acc
| len == n = [acc]
| otherwise = do
let k = len + 1
p = if k == 1 then 1 else last acc + 10
q = m - 10 * (n - k)
a <- [p .. q]
resolve n m (acc `snoc` a)
where
len = length acc
```
## [E - Expansion Packs](https://atcoder.jp/contests/abc382/tasks/abc382_e) (upsolve)
まず先に「パックをひとつ開封したとき レアを $x$ 枚引く確率」を $x$ ごとに求めます。
これは確率 DP で求められる。
これがあれば、$i = 0 \ldots X$ の遷移過程で「レアカードを $i$ 枚引いた時点」から、さらにパックを一つ開ける次の状態にどういう確率で遷移するかがわかります。あとは期待値 DP です。
というところまでは分かったのですが、後者の期待値 DP がうまくいかず。
原因は、パックを開けたがレアカードが $0$ 枚である、というケースへの対応ができなかったことにありました。
結論、確率/期待値 DP でよくある「自己ループ除去」が必要でした。
ardririy さんの [ABC382 | ardririyの足跡](http://trail.ardririy.net/article/ABC382) から式を拝借
$\begin{align}E(x) &= 1 + \sum_{i=1}^N P(i)E(\text{max}(x-i, 0)) + P(0)E(x) \\E(x) &= \frac{1 + \sum_{i=1}^N P(i)E(\text{max}(x-i, 0))}{1 - P(0)}\end{align}$
とすることで $E(x)$ が両辺に出てくる自己ループを除去できます。
その上で期待値DP、でした。
```haskell
main :: IO ()
main = do
[n, x] <- getInts
ps <- getInts
let prob = accumArrayDP @UArray f (+) (0 :: Double) (0, n) [(0, 1.0)] [fromIntegral p / 100 | p <- ps]
where
f (i, acc) p
| acc == 0 = []
| otherwise = [(i, acc * (1 - p)), (i + 1, acc * p)]
let ans =
let dp = listArray @Array (0, x) $ 0 : [f i | i <- [1 .. x]]
where
f i =
let s = sum [dp ! max 0 (i - j) * prob ! j | j <- [1 .. n]]
in (s + 1) / (1 - prob ! 0)
in dp ! x
print ans
```
## [F - Falling Bars](https://atcoder.jp/contests/abc382/tasks/abc382_f) (upsolve)
コンテスト中は問題文を読むこともせず。翌朝に upsolve しましたが、明らかに E より F の方が簡単 ···
というよりは競プロ典型 90問の [029 - Long Bricks（★5）](https://atcoder.jp/contests/typical90/tasks/typical90_ac) とほぼ同じ問題でした。こっちを解くべきでした。
初期状態で与えられたブロック群が、テトリスのように時間経過と共に下に落ちていく。
もうそれ以上動かない、という安定状態になったときに、各ブロックの位置する高さを求める。
直感的に考えても、初期状態で下の方にあるブロックから貪欲に考えていけばよさそう。
そしてその貪欲戦略を採用すると先の類題と全く同じ問題になります。
遅延伝搬セグメント木を使って次のブロックの幅である $[l, r)$ 区間のその時点での最大の高さを求める。
それがそのブロックを置ける高さです。そして、ブロックを置くからには $[l, r)$ 区間の最大の高さを区間更新で $+1$ する。
これでブロックの高さが決まっていきます。
```haskell
main :: IO ()
main = do
[h, w, n] <- getInts
xs <- replicateM n getTuple3
let qs = sortOn' (Down . snd3) [(i, ri, (ci, ci + li - 1)) | (i, (ri, ci, li)) <- indexed 1 xs]
tree <- newListLST @IOUArray (w + 1) max minBound max 0 max $ replicate w (0 :: Int)
res <- for qs $ \(i, _, (l, r)) -> do
hi <- rangeQueryLST tree l (r + 1)
rangeUpdateLST tree l (r + 1) (hi + 1)
return (i, hi)
let hs = array @UArray (1, n) res
for_ [1 .. n] $ \i -> do
print $ h - hs ! i
```
## 感想など
今回の問題セットのように E よりも F の方が簡単、というケースがときどきあります。
どうやって E を切って F にいくかですが、ぱっと見、得意そうな問題かどうかでこれまでは判断していました。
今回の期待値DP は、過去問を結構やりこんでいたのでいけるかなーと思い、F をみずに E に執着してしまいました。
実際、結構いいところまではいって、それが故に損切りできず、という感じでもありました。
でも、この損切り方針はあまりよくなさそう。問題文の読解スピードを上げて、E と F を同時に問題としては理解して
その上でどちらを先に解くか判断するのが本筋なんでしょう。
思考プロセスとしては「問題文読む → 表面的にどんな問題か判断する → 制約含め問題の構造を理解する → 解法を考察する → 実装する」という段階を踏みますが、いまは「表面的に···」のところで判断しています。ここを「制約含め問題の構造を理解する」までやってから、 E or F どちらを着手するか決めることができれば、今回のようなケースに対応できたのかもしれないなと思いました。特に今回は類題があったので、 F は 10分もかからず解けていたと思います。
悔しい!