# ABC358 振り返り
- [CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358) - AtCoder](https://atcoder.jp/contests/abc358)
- ABCD 4完 (1187) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc358)
![[スクリーンショット 2024-06-16 8.15.23.png]]
ABC358 でした。
E が難し目だったため、実質 ABCD 4問の早解き回になりました。
その4問も比較的素直な典型問題が多く、10分程度で解いてる方もちらほらいました。
- A (灰) ··· 文字の一致判定
- B (灰) ··· 現在時刻と $T_i$ どっちが優先されるかを判定
- C (灰) ··· ビット全探索
- D (灰) ··· 貪欲法。ソートして小さい方から、その小さい方に一番近い箱を探す。IntMultiSet を使う
- E (水, upsolve) ··· その時点での文字列長を状態にナップザックDP。新たな文字を加えるケースの増加を二項係数の積で考える
でした。
これぐらい典型問題になってくると、bit 全探索や multiset が要求されるような問題でももはや 灰色 diff という...
一昔前ならビット全探索は茶色、multiset の探索がでてくると緑ぐらいという印象でしたが、レベルの底上げが進んでいるのでしょうか。
## [A - Welcome to AtCoder Land](https://atcoder.jp/contests/abc358/tasks/abc358_a)
これはやるだけです。
```haskell
main :: IO ()
main = do
(s, t) <- auto @(String, String)
printYn $ s == "AtCoder" && t == "Land"
```
## [B - Ticket Counter](https://atcoder.jp/contests/abc358/tasks/abc358_b)
地味に ABCD の中ではこの問題が、認知負荷が一番高かったです。
売り場に並ぶ、とか列の最後尾に並び、みたいな問題文に惑わされてしまいました。
が、冷静に考えると現在時刻が $T_i$ を過ぎていたら即座にチケットを買える、過ぎていなかったら $T_i$ になるのを待つ。
チケット購入で $+ A$ 秒進む。
これだけなので、現在時刻を状態として、それが $T_i$ を過ぎてるかどうかを判定すれば OK。
出力には履歴がすべて必要なので `scanl'` を使います。
```haskell
main :: IO ()
main = do
[n, a] <- getInts
ts <- getInts
let res = scanl' (\cur t -> max cur t + a) 0 ts
for_ (tail res) print
```
## [C - Popcorn](https://atcoder.jp/contests/abc358/tasks/abc358_c)
ビット全探索の問題。制約の $1 \leq N, M \leq 10$ ですぐにわかります。
「ビット全探索」といいつつそれは他のプログラミング言語での実装が元になった手法名で、Haskell 的にはリストの冪の全列挙です。
`subsequences` を使います。
```haskell
ghci> subsequences [1 ..3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```
あとは、それぞれのパターンで全種類のポップコーンを買えるかチェック。こちらは各ポップコーン店の扱う商品の集合を和 $\cup$ で畳み込んで、$M$ 個になったかを数えればよいでしょう。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
ss <- replicateM n getLine
let ss' = [Set.fromList [i | (i, c) <- indexed 1 s, c == 'o'] | s <- ss]
res = [length xs | xs <- subsequences ss', Set.size (foldl' Set.union Set.empty xs) == m]
print $ minimum res
```
我ながら良い実装だと思います。
### BitSet を使う
そういえば集合の表現には拙作の BitSet が使えます。
BitSet 使える場面でもなかなか使えないマンです。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
ss <- replicateM n getLine
let ss' = [fromListBS [i | (i, c) <- indexed 1 s, c == 'o'] | s <- ss]
res = [length xs | xs <- subsequences ss', sizeBS (foldl' unionBS emptyBS xs) == m]
print $ minimum res
```
## [D - Souvenirs](https://atcoder.jp/contests/abc358/tasks/abc358_d)
$A$ と $B$ 二つの系列があって、$B_i$ 以上の $A_i$ とのマッチング。
なんとなくソートや $O(\log n)$ の探索をすることが浮かびます。
この問題では $B_i$ に対応する $A_i$ を、すべての $B_i$ に対して見つける必要があります。
またある $B_i$ に対して、大きすぎる $A_i$ をマッチングさせるのは悪手です。
となると $B_i$ を小さい方からみていって、$A_i$ の中でベストマッチなものを、その $B_i$ に充てるという貪欲法が成立するのがわかります。
ベストマッチを探すには「その時点で $A$ に残っているものの中から $B_i$ 以上のもの」を効率的に探せる必要があります。
そしてマッチングした場合は、みつかった $A_i$ は候補から取り除く必要もあります。
- 集合からの削除に対応したデータ構造
- ある値以上の値があるかを効率的に探索できる
- $A_i$ は同じ値が複数ある
この要件を満たすのは順序付き多重集合です。IntMultiSet (cojna さん作のものを移植した盆栽) を使います。
`mapAccumL` でその時点の集合を状態として持ち、都度、多重集合から $B_i$ に対するベストマッチを探索して削除。
見つかった値は Maybe で表現しておいて `sequenceA` で評価することで、マッチングが途中で失敗したかどうかも含めて計算します。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
bs <- sort' <
gt; getInts
let s0 = fromListMS as
let (_, res) = mapAccumL f s0 bs
where
f s b = do
case lookupGEMS b s of
Just x -> (deleteMS x s, Just x)
Nothing -> (s, Nothing)
case sequenceA res of
Nothing -> print (-1 :: Int)
Just xs -> print $ sum xs
```
## [E - Alphabet Tiles](https://atcoder.jp/contests/abc358/tasks/abc358_e) (upsolve)
DP です。DP なのはみればわかるわけですが、状態遷移の構築がなかなか難しく、結果解けませんでした。
[(152) 4分でAtCoder Beginner Contest 358 A-G【ゆっくり解説】 - YouTube](https://www.youtube.com/watch?v=nMfaeNz03jA) がわかりやすかったです。
そこから抜粋。
![[スクリーンショット 2024-06-16 7.37.21 1.png]]
ある時点で文字の長さが $2$ 文字だったとします。
```
AA
```
そこに、ほかの文字を $3$ つ使うとする。
```
AA + BBB
```
合計 $5$ 文字になるとき、`B` $3$ 文字を加えてとりうる文字列のパターンは $5$ 文字中 $3$ 文字の位置を選ぶするケースなので $_5C_3$
次に別の文字 `C` を $4$ 文字使うとする。この場合同様の考え方で $_{9}C_4$ となる。
最初の `A` のケース $_2C_2 = 1$ と続くケースの積を取ると $_2C_2 \times _5C_3 \times _{9}C_4$ となって、これが $10$ 文字に A2 B3 C4 使うときのパターン数になる。
A2 B3 の 5文字の状態と、C を 4 つ加えて 9 文字になる状態の間には依存がある (独立でない)。
依存があるときの場合の数の結合なので、積を使う。
なるほどー、言われてみれば...。
なお DP 的に考えると A から順番にやっていくのでほんとにいいのかと疑問に思いますが
```
AA + BBB → (例) BBABA
```
のように B を A よりも前の位置に挿入するケースも包含するのでこれで問題ない。
結局、$A$ から $Z$ まで順番にみていってその都度、その文字を「使う、使わない」を選択。使う場合は何文字を使うか考える。
各局面で、現在の文字列長が何文字かを知る必要があるので、それを状態として DP ... となるので計算の構造的にはナップザック問題です。
そこに二項係数の積という計算を持ち込むことができるか、というのが問われる問題でした。ここが難しかった。
なお $_nC_r \mod 998244353$ を計算する実装を予め持ってないとちょっときついかもしれないです。
```haskell
main :: IO ()
main = do
k <- getInt
cs <- getInts
let dp = accumDP @Array f (+) (0 :: IntMod) (0, k) [(0, 1)] cs
where
f (len, acc) ci
| acc == 0 = []
| otherwise = [(len + i, acc * combMod (len + i) i) | i <- [1 .. ci]]
IntMod ans = sum [dp ! i | i <- [1 .. k]]
print ans
```
## 感想など
ミスもなく早解きできたのでパフォーマンスは 1187 出て、レートは少し上昇し 1067 になりました。
ここ数回微減が続いていたので、多少の増加とは言え相殺できて良かったです。
とはいえ、E を 80 分かけて考察して解けなかったのは反省が残ります。
二項係数とかその辺は、手元でいろいろこねくり回していたのですがちょうどよい定式化にもっていくことができず、でした。
精進は相変わらず PAST の過去問をやっています。
が、だいぶそれも進捗していて高難度問題を除くとストックがだいぶ減ってきました。
全部終わったら PAST 受けてみましょうかね。いまの実力ですと上級は難しそうですが、おそらく中級はいけると思います。
![[スクリーンショット 2024-06-16 9.11.08.png]]
引き続きコツコツがんばります。