# ABC384 振り返り
- [トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384） - AtCoder](https://atcoder.jp/contests/abc384)
- ABCDE 5完 (1088) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc384)
![[スクリーンショット 2024-12-15 11.31.19.png]]
ABC384 でした。
5完できたものの難易度的には普段よりもやや低め、5完早解き回という感じで結局パフォーマンス 1088 で奮わず。4 ペナもらったのが響きました。
- A (灰) ··· 問題文通りに $S$ を写像する
- B (灰) ··· これも問題文通りに実装するだけ
- C (灰) ··· `subsequences` で `ABCDE` の部分列を全部列挙して、スコアでソート
- D (茶) ··· $r = S \mod \sum{A}$ を累積和で作ることができるか、二分探索で累積和テーブルを探索。円環データ構造にするとよい
- E (緑) ··· 順序付き集合で「併合したスライムに隣接している、まだ併合していないスライム」を管理する。そこから貪欲に、最も弱いスライムを取り出し併合していけば OK。オーバーフローに注意
でした。
## [A - aaaadaa](https://atcoder.jp/contests/abc384/tasks/abc384_a)
$S$ の文字のうち $c_1$ であるもの以外を全て $c_2$ に置き換える。その通りに写像すれば良いです。
```haskell
main :: IO ()
main = do
(_, c1, c2) <- auto @(Int, Char, Char)
s <- getLine
let s' = map f s
where
f c
| c == c1 = c
| otherwise = c2
putStrLn s'
```
## [B - ARC Division](https://atcoder.jp/contests/abc384/tasks/abc384_b)
問題文の指示通りに実装する。パターンマッチとガードで分解すると綺麗に整理できます。
```haskell
main :: IO ()
main = do
[n, r] <- getInts
qs <- replicateM n getTuple
let ans = foldl' f r qs
where
f acc (1, ai) | inRange (1600, 2799) acc = acc + ai
f acc (2, ai) | inRange (1200, 2399) acc = acc + ai
f acc _ = acc
print ans
```
## [C - Perfect Standings](https://atcoder.jp/contests/abc384/tasks/abc384_c)
`ABCDE`の空ではない部分列すべてを生成するのは `subsequences` を使えば良いです。
あとは Array を使って `A` 〜 `E` を索引にスコアのテーブルを作り写像。
同点の場合は辞書順で小さい方を優先する必要があるので、部分列を先にソートしておき、それからスコアでソートする。
Haskell の sort は安定ソートなので、これでうまくいきます。
```haskell
main :: IO ()
main = do
[a, b, c, d, e] <- getInts
let table = listArray @UArray ('A', 'E') [a, b, c, d, e]
toScore s = sum' $ map (table !) s
res = sortOn (Down . snd) [(s, toScore s) | s <- sort $ subsequences "ABCDE", notNull s]
for_ res $ \(s, _) -> do
putStrLn s
```
## [D - Repeated Sequence](https://atcoder.jp/contests/abc384/tasks/abc384_d)
周期 $N$ ということで、$S \bmod{\sum{A}}$ を考えるとよいです。
$S$ を構成する部分和のうち $\sum A$ の繰り返しの和だけでは作れない数、つまり $S \mod \sum A$ を、$A$ の連続部分列の和で作る事ができれば答えは `Yes` になる。
$A$ の連続する部分列の和は、累積和で表現できこれは単調増加なので二分探索が使える。
$r = S \mod \sum{A}$ とし累積和の系列を $s$ とすると $r = s_j - s_i$ なる $s_j$ と $s_i$ の組みが $s$ の中に存在すればよいことになります。
$s_j$ を固定すると $s_i = s_j - r$ となるので、これが $s$ にあるかを二分探索で見つける。
このとき $A$ は無限リストなので、累積和 $s$ を $A$ を二つ繋げた円環データ構造で表現してやると、うまくいきます。
本番では円環にせずに実装してしまい、WA を出し、コーナーケース間違えたか? とごちゃごちゃいじり初めて 3 ペナもらってしまいました。不覚。
結論、円環をちゃんとやれば以下のようなシンプルな実装で済みました。
```haskell
main :: IO ()
main = do
[n, s] <- getInts
as <- getInts
let cs = listArray @UArray (0, 2 * n) $ scanl' (+) 0 (as ++ as)
r = s `mod` sum' as
res = or [lookupLE (sj - r) cs == Just (sj - r) | sj <- elems cs]
printYn res
```
## [E - Takahashi is Slime 2](https://atcoder.jp/contests/abc384/tasks/abc384_e)
高橋君が現在併合しているマスをグラフの頂点ととらえる。
すると、グラフに隣接しているまだ併合していない頂点の中から、最も弱いスライムを併合していくのが最適そう。貪欲法で OK です。
問題は「その時点でグラフに隣接している併合していない頂点の中の最小値」を求めるところ。
BFS や Union-Find なんかでシュッとはいかなそう。
よく考えると、行動1回につき1頂点しか併合されない。併合された頂点の隣接頂点の高々 $4$ 個が併合候補の中にその都度加えられていく程度です。
その時点で併合できるマスの候補を集合で管理出来れば良さそう。
順序付き集合なら、集合に含まれている候補の中からもっとも小さな値をもつ元を探すこともできます。
というわけで Set に $(S_{i,j}, (i, j))$ というタプルを入れて、その時点で併合可能なマスの集合を管理しながら再帰を回し、アキュムレータに強さを加算していきます。
集合が空っぽになるか、集合から取り出した最小値がその時点の強さの $\frac{1}{X}$ 以上であったらそこで行動終了。
既存のグラフアルゴリズムを貼るだけというわけにはいかなそうだったので、素で実装です。
$\frac{1}{X}$ 未満の判定を最初 `x * next < acc` としていたらオーバーフローして 1 ペナ。多倍長整数を使うか、`next < acc ceildiv x` とする必要がありました。
Haskell だとどうしても、こういうとき実装にちょっと時間を要してしまいます。
1ペナ取り除くまでのデバッグも含めて 30 分以上掛かってしまいました。
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)]
loop grid x visited acc h
| Set.null h = acc
| next < acc `ceildiv` x =
let us = [u | d <- lrud, let u = v + d, inRange (bounds grid) u, Set.notMember u visited]
h'' = foldl' (flip Set.insert) h' [(grid ! u, u) | u <- us]
visited' = foldl' (flip Set.insert) visited us
in loop grid x visited' (acc + next) h''
| otherwise = acc
where
((next, v), h') = Set.deleteFindMin h
main :: IO ()
main = do
[h, w, x] <- getInts
v0 <- getTuple
grid <- getIntGrid ((1, 1), (h, w))
let us = [u | d <- lrud, let u = v0 + d, inRange (bounds grid) u]
visited = Set.fromList $ v0 : us
h0 = Set.fromList [(grid ! u, u) | u <- us]
ans = loop grid x visited (grid ! v0) h0
print ans
```
## 感想など
A, B, C がだいぶ簡単だったので、そのまま早解き脳で D に取り掛かった結果、すこし焦ってしまいました。
やはり D あたりからは焦って解こうとしてはダメですね、しっかり考察して落ち着いて実装すべき。
最近は D, E あたりで解法が全然見えないということは少なく、いかに考察をしっかりやって精度高く実装できるが勝負の分かれ目になってきています。
その状況にフィットしていく必要があります。
ここ数回はそれができていたのですが、今回のように C が簡単すぎると脳をスイッチできずに D に突入してしまうので、一息つく癖をつけたい。