# ABC323 振り返り
- [ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323) - AtCoder](https://atcoder.jp/contests/abc323)
- 成績 ABCD 4完 (959) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc323)
ABC323 でした。
パフォーマンス 959 で緑パフォーマンス、レートは微増、という成績でした。
緑 diff の D 問題まで解くことができました。適正難易度の問題をきちんとこなせており AC 数的には満足です。一方、速度面ではちょっと実装が遅かったです。4完でも実装が速ければパフォーマンス 1000 以上は取れた模様。
C, D ともにやや必要以上に実装が複雑になってしまったところが、実装の遅さの原因でした。
特に D は、提出したコードは AC はできたものの、やらなくていいことまでやってしまい時間をかけすぎました。
![[スクリーンショット 2023-10-08 0.50.13.png]]
- A 問題 (灰) ··· 偶数の要素のみ抜き出して `all (== 0)` で判定
- B 問題 (灰) ··· 素直に計算してソートして出力
- C 問題 (灰) ··· 要素数が $100 \times 100$ 程度しかないので、ナイーブに計算して OK
- D 問題 (緑) ··· `IntMap` を使って整数の個数を管理。小さな整数から順に合成していき、確定した整数をカウントアップする
- E 問題 (水、未完) ··· 確率DP
という問題セットでした。
65分くらいまでに D を解けていればパフォーマンス 1000 といったところで、仮に 1000 を取るのを目標とすると10分ほど遅かったです。
なお、振り返ればアルゴリズム的な知識が要求されるのは E 問題以降で、D まで全てナイーブな実装で良いという、やや特殊な問題セットでした。
----
## [A - Weak Beats](https://atcoder.jp/contests/abc323/tasks/abc323_a)
問題文にある通り、偶数番めの文字を抜き取って全部 `0` か否かを調べる。
```haskell
main :: IO ()
main = do
s <- getLine
let xs = map snd $ filterOnFst even $ zip [1 :: Int ..] s
putStrLn $ if all (== '0') xs then "Yes" else "No"
```
[提出 #46280819](https://atcoder.jp/contests/abc323/submissions/46280819)
---
## [B - Round-Robin Tournament](https://atcoder.jp/contests/abc323/tasks/abc323_b)
素直に勝敗表をなぞって各プレイヤーの勝利数を数え上げて、ソートして出力。
Haskell の `sort` は安定ソートなので、プレイヤー番号の方は気にせず勝数の降順でソートで OK。
```haskell
main :: IO ()
main = do
n <- getInt
ss <- replicateM n getLine
let xs = zip [1 :: Int ..] $ map (sum . map f) ss
where
f 'o' = 1
f '-' = 0
f 'x' = 0
xs' = map fst $ sortOn (Down . snd) xs
putStrLn . unwords . map show $ xs'
```
- [提出 #46287253](https://atcoder.jp/contests/abc323/submissions/46287253)
----
## [C - World Tour Finals](https://atcoder.jp/contests/abc323/tasks/abc323_c)
初見では二分探索で、各プレイヤーが解くべき問題数を調べるとかかなと思いましたが、制約を見るに $N$ も $M$ も高々 $100$ 程度なので線形探索で十分。これは特にアルゴリズムを使わずに、丁寧に実装すればいい問題 ... ということでやっていくわけですが結構めんどくさくて時間がかかりました。
結局 25分近くかけてしまいました。このぐらいの実装が必要な場合も、5分10分でさっと済ませられるようになりたいものです。
まず、全部プレイヤーの中の最大スコア $X$ を出します。この最大スコアを超えるのが、各プレイヤーの目標です。
次に、各プレイヤーごとにまだ解いてない問題をスコアの高い順に見ていって、$X$ を超えるまで解く。解いた問題の数が答え。
割と単純なんですが、データ構造の組み方を焦って適当にやると沼りそうな感じの問題でした。
```haskell
solve x score record as = do
let as' = map snd $ filter (\(i, _) -> not (record ! i)) as
length $ takeWhile (< x) $ scanl (+) score as'
main :: IO ()
main = do
[n, m] <- getInts
as <- getIntsArray (1, m)
ss <- replicateM n getLine
let records = [listArray @UArray (1, m) $ map (== 'o') s | s <- ss]
scores = [[as ! i | (i, _) <- filter snd (assocs rs)] | rs <- records]
scores' = zipWith (\i score -> sum score + i) [1 ..] scores
x = maximum scores'
as' = sortOn (Down . snd) $ assocs as
forM_ (zip scores' records) $ \(score, record) -> do
print $ solve x score record as'
```
----
## [D - Merge Slimes](https://atcoder.jp/contests/abc323/tasks/abc323_d)
ようやく、アルゴリズムなりデータ構造なりをちゃんと考える必要のある問題かと思いましたが、これまた貪欲法でした。
データ構造に `IntMap` を使う工夫が必要だった、ぐらいです。
スライムの種類と、何匹いるかを `IntMap` で管理します。
シミュレーションで、$2$ 匹以上いるスライムを `IntMap` から取り出して、合成して `IntMap` に戻します。
(取り出したスライムが $1$ 匹の場合は合成できないので、戻しません。)
これを再帰的に繰り返します。
ヒープなどではなく `IntMap` を使うのは、合成後にスライムは $2X$ サイズになるわけですが、すでに場に $2X$ サイズのスライムが既存でいた場合それらと数をマージする必要があるからです。
基本はこれで良いわけですが、計算の順序と終わりを考えなければいけません。
スライムを合成するとサイズ $X$ のものは $2X$ になる、つまりサイズが増加します。よって、その時点で最小のスライム $X$ を合成した場合はもうその $X$ サイズは二度と触ることがありません。つまりサイズの小さなスライムから貪欲に処理していけば良く、一度処理したスライムはもうそれで答えに対する寄与数が確定します。スライムが奇数匹の場合、合成しても余りが一匹出てしまいますがその一匹はもう合成には使われないのが確定しているのでその数を数えておきます。
これを `IntMap` が空になるまで繰り返すと、余ったスライムを数えていたアキュムレータにもう合成に使えないスライムの種類数、つまり答えが累積されている... という算段です。
落ち着いて考えれば割と簡単で、実装もシンプルです。
```haskell
solve bucket x
| IM.null bucket = x
| otherwise = do
let ((i, cnt), bucket') = IM.deleteFindMin bucket
(p, q) = cnt `divMod` 2
x' = x + q
if p > 0
then solve (IM.insertWith (+) (i + i) p bucket') x'
else solve bucket' x'
main :: IO ()
main = do
n <- getInt
xs <- replicateM n getTuple
let bucket = IM.fromListWith (+) xs
ans = solve bucket 0
print ans
```
が、本番では考察が甘くて、必要以上に実装を複雑化させてしまいました。
先に書いた通り、その時点で最小サイズのスライムから貪欲にやっていけば一度合成したサイズのスライムはそこで答えに対する寄与数が確定するわけですが、その考察が十分でなかったためわざわざスライムの数が $2$ 匹以上の集合と、$1$匹の集合とに分けて管理して合成して$1$匹余ってももう $1$ 匹いたらそいつと足して $2$ 匹になって... という面倒な計算をしてしまいました。余計な考慮をしたせいで、実装が複雑になってしまい時間がかかりました。しかも1回ペナルティをもらってしまいました。
```haskell
fn bucket s
| IM.null bucket = (bucket, s)
| otherwise = do
let ((i, cnt), bucket') = IM.deleteFindMin bucket
(p, q) = cnt `divMod` 2
if p >= 2
then do
let bucket'' = IM.insertWith (+) (i + i) p bucket'
s' = if q == 1 then IS.insert i s else s
fn bucket'' s'
else do
if IS.member (i + i) s
then do
let bucket'' = IM.insert (i + i) 2 bucket'
s' = IS.delete (i + i) s
s'' = if q == 1 then IS.insert i s' else s'
fn bucket'' s''
else do
let s' = IS.insert (i + i) s
s'' = if q == 1 then IS.insert i s' else s'
fn bucket' s''
main :: IO ()
main = do
n <- getInt
xs <- replicateM n getTuple
let bucket = IM.fromListWith (+) $ filterOnSnd (>= 2) xs
s = IS.fromList $ map fst $ filterOnSnd (== 1) xs
(bucket', s') = fn bucket s
print $ IS.size s'
```
[提出 #46342369 ](https://atcoder.jp/contests/abc323/submissions/46342369)
----
## [E - Playlist](https://atcoder.jp/contests/abc323/tasks/abc323_e) (未完 🍊)
確率DP の問題です。
確率DP は理解が曖昧なので学習します!
----
## 感想など
できればパフォーマンス 1000 は出したかったですが、まあ及第点です。
ここ数回の試行錯誤でメンタルコントロールがうまくできるようになってきた感があり、これは結構自分的に収穫です。
C や D で実装が多少ごちゃついても、慌てずに解き切ることができたのはその賜物だと思います。
一方、本番でなければ実装が複雑になりそうだったら一旦立ち止まってシンプルに留められる方法がないかじっくり考えるんですが、今回は考え切らずに実装を始めてしまって結果的にごちゃついて余計時間がかかりました。平時に同じく複雑化しない実装の方法を練るなど思考し切れるよう、自身のマインドを制御できるようになるのが次の目標ですね。