# ABC326 振り返り
- [パナソニックグループ プログラミングコンテスト2023（AtCoder Beginner Contest 326） - AtCoder](https://atcoder.jp/contests/abc326)
- 成績 ABC3完 (894) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc326)
ABC326 でした。
前回と同じようなところをうろうろしています。
![[スクリーンショット 2023-10-29 13.25.59.png]]
- A問題 (灰) ··· やるだけ、なんですがちょっと問題文に癖がある
- B問題 (灰) ··· 全探索。$10$ 進数を分解して条件判定。
- C問題 (灰) ··· 全探索 + 二分探索もしくは、しゃくとり法
- D問題 (水) ··· 重実装問題···? permutations で全列挙に気づけば比較的実装量を抑えられる
- E問題 (水) ··· 期待値DPを累積和で高速化
という問題セットでした。
結果的には、緑色である私のレート帯的には ABC をいかに早く解くか、また D or E をどちらか一つでいいから通せるか? という勝負でした。
D を少し考えてみたものの、なかなか探索のための良いアイデアが思いつかなかったので、E に着手しました。期待値 DP なのはわかったのですが、こちらもうまく構成できず。
D or E を通せなかったのは悔しいところですが、ABC ぐらいまでシュッと行けましたし安定感は出てきたと思います。ここ2ヶ月ぐらいひたすら ABC の緑 diff を解いていましたが、大体の問題を 2 〜 4回解いたのでそろそろ、より高難度の問題の精進に入っていこうと思います。
あとは前回同様、実装スピードですね。前回もそうですが、今回のような難易度構成だと ABC を早解きできるかどうかも重要になってくるので、速いは正義です。
----
## [A - 2UP3DOWN](https://atcoder.jp/contests/abc326/tasks/abc326_a)
条件判定問題。
```haskell
solve x y
| x < y && y - x <= 2 = True
| x > y && x - y <= 3 = True
| otherwise = False
main :: IO ()
main = do
[x, y] <- getInts
putStrLn $ if solve x y then "Yes" else "No"
```
簡単な問題ではあるのですが「 $2$ 階分までの上り、または、$3$ 階分までの下り」という聞き慣れない文章と開始直後の緊張も相まってか、少し理解するのに時間がかかってしまいました。
この A を通した時点で 4:33 でした。TL をみてると 4:32 で C まで通してる人もいて、やばいです。
----
## [B - 326-like Numbers](https://atcoder.jp/contests/abc326/tasks/abc326_b)
$3$ 桁の整数を $10$ 進数として分解して、326-like number なる数字かどうかを判定する。
326-like number は必ず 3桁ですし、答えがあることは保証されているので素直に全探索すれば OK です。
```haskell
is326 x = do
let [a, b, c] = toDigits 10 x
a * b == c
main :: IO ()
main = do
n <- getInt
let result = filter is326 [n ..]
print $ head result
```
A より B の方が🧠への負荷は小さかった気がします。
---
## [C - Peak](https://atcoder.jp/contests/abc326/tasks/abc326_c)
しゃくとり法なのはすぐわかりましたが、あまり慣れていないしゃくとり法で実装すると細かいところで沼りそう、かつこの問題は二分探索でもいけるので、安全目に倒して二分探索で実装しました。
```haskell
solve n m as x = do
let (ng, _) = bisect2 (0, n + 1) (\i -> as ! i < as ! x + m)
(ng + 1) - x
main :: IO ()
main = do
[n, m] <- getInts
as_ <- getInts
let as = listArray @UArray (1, n) (sort as_)
print $ maximum $ map (solve n m as) [1 .. n]
```
これが灰色なのかあと、恐ろしい話です。
気をつけないと境界条件ではまりそうな問題なので、焦る気持ちを抑えて丁寧に実装。一発で通って良かったです。(小学生並みの感想)
ちなみに、コンテスト後にしゃくとり法で実装し直しました。
しゃくとり法は [Haskellでしゃくとり法を攻略する](https://zenn.dev/osushi0x/articles/e5bd9fe60abee4) を参考に、二項演算を高階関数で渡すように `shakutori` 関数として抽象化しています。が、案の定、慣れてないこともあってちょっと時間がかかりました。
二分探索にしておいて正解でした。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
as_ <- sort <
gt; getInts
let as = listArray @UArray (1, n - 1) $ zipWith (-) (tail as_) as_
secs = shakutori (1, n - 1) (as !) (+) (-) 0 (\acc r -> acc + r < m)
ans = succ . maximumWithDefault 0 $ map (\(l, r) -> r + 1 - l) secs
print ans
```
----
## [D - ABC Puzzle](https://atcoder.jp/contests/abc326/tasks/abc326_d) (upsolve)
問題の制約からして、全パターンを構成して判定することを匂わせます。
コンテスト中にはうまい探索方法が見つけられず、断念しました。
条件を満たすグリッドにおいては
- `A` は各行各列に必ず 1 回ずつ出てくる。つまり、`AAAAA` という5つの A をそれぞれ何行目に置くかという順列 $5!$ パターンを考えれば良い
- `B` と `C` も同様
というわけで、実は $5! = 120$ の $120^3 = 1728000$ で $10^6$ なので全部試せますよ、というところに気がつけるかどうかでした。
`A` `B` `C` の出現位置を全部生成しても計算可能だということがわかれば、あとはただ実装するだけ。`permutations` で `A` `B` `C` それぞれの出現位置を全列挙して、`sequence` でその直積集合を得ます。直積の元を `accumArray` でまとめ上げれば $120^3$ 個のグリッドの出来上がりです。
あとはグリッドから、$R$ と $C$ と比較するための文字列を抜き取って判定です。
```haskell
toGrid n = accumArray @UArray (flip const) '.' ((1, 1), (n, n))
rowHeads grid = do
let rows = chunksOf n (elems grid)
map (head . filter (/= '.')) rows
where
(_, (_, n)) = bounds grid
colHeads grid = do
let cols = transpose $ chunksOf n (elems grid)
map (head . filter (/= '.')) cols
where
(_, (_, n)) = bounds grid
isOk r c grid
| any (\row -> length (filter (/= '.') row) /= 3) (chunksOf n $ elems grid) = False
| rowHeads grid /= r = False
| colHeads grid /= c = False
| otherwise = True
where
(_, (_, n)) = bounds grid
main :: IO ()
main = do
n <- getInt
r <- getLine
c <- getLine
let as = [map (,'A') (zip [1 ..] xs) | xs <- permutations [1 .. n]]
bs = [map (,'B') (zip [1 ..] xs) | xs <- permutations [1 .. n]]
cs = [map (,'C') (zip [1 ..] xs) | xs <- permutations [1 .. n]]
xss = sequence [as, bs, cs]
let gs = filter (isOk r c) $ map (toGrid n . concat) xss
if null gs
then putStrLn "No"
else do
putStrLn "Yes"
mapM_ putStrLn $ chunksOf n (elems $ head gs)
```
コンテスト中は「重実装っぽいなー、これは罠」と思ってましたが、終わってみれば、事前の正確な計算量見積もりができればスマートなやり方が見つかる良問だった気がします。
----
## [E - Revenge of "The Salary of AtCoder Inc."](https://atcoder.jp/contests/abc326/tasks/abc326_e) (upsolve)
出ました期待値DP。確率DP、期待値DP はよく出ますね。
確率・期待値DP は水色の登竜門だということがわかってきました。
今回の問題は [[ABC263 E - Sugoroku 3]] 同様に、期待値DP をただするだけでは難しいので、セグメント木や Binary Indexed Tree などで区間和を高速に取得できると良い問題です。
DP の構成の仕方は前からやる、後ろからやる、どちらでも良さそうですが私は後ろからやりました。
- $dp(x)$ を「現在が $x$ のとき、そこからダイスを降ってもらえる金額の期待値」とする
- $dp(n) = 0$ ··· $x = n$ のときはダイスをそこから振っても必ずゲームが終了するため
- この $dp(n)= 0$ を足場に、DP を開始する。つまり $n$ から $0$ の方に進んで答えが $dp(0)$ になるパターン
- $dp(i)$ からみると、次のトライでは $A_{i + 1} \ldots A_n$ までの値を確率 $\frac{1}{N}$ でもらえる。これが次のトライで手に入る給料の期待値
- 加えて、それまでの累積期待値 $dp(i + 1) \ldots dp(n)$ も乗ってくる
と考えます。実装としては
- $A_{i + 1} \ldots A{n}$ を毎回計算する必要があるのであらかじめ $A$ の累積和をとっておく
- $dp(i + 1) \ldots dp(n)$ は動的な区間和なのでセグメント木や Binary Indexed Tree を使うと楽。
としました。
区間和でいいなら BIT の方が簡単に使えるので、BIT を選択しました。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let s = listArray @UArray (1, n + 1) $ scanl' (+) 0 as
dp <- newBIT @IOArray (0, n)
forM_ [n - 1, n - 2 .. 0] $ \i -> do
let a = s ! (n + 1) - s ! (i + 1)
b <- rangeSumBIT dp (i + 1) (n + 1)
let x = (IntMod a + b) * invIntMod (IntMod n)
incrementBIT dp i x
IntMod ans <- rangeSumBIT dp 0 1 -- dp(0)
print ans
```
確率・期待値DP は、2週間ほど前に過去問を $10$ 問ほどやってはいたものの、本番中には解けず。過去問を $1$ 回ずつやった程度では、まだ身体化できてないことがよくわかります。
計算の構造にはなんとなく気づけたものの、いざ実装してみると手が動かなかったです。
期待値DPや確率DP にはある程度パターンがあるので、まずはそれを身体化するところまで持っていきたいです。コモディティな部分はパターン認識で済ませて認知エネルギーを節約できれば、問題の本質的なところに思考を集中させることができます。
----
## 全体を通しての感想
今週は木曜日に Qiita カンファレンスがあり、その発表の準備などもあってあまり精進できていなかったので、本戦に響かないかどうか心配でしたが杞憂でした。
冒頭にも書いた通り、簡単な問題への対応力はおかげさまで安定力が増してきている感があるので、改めて確率・期待値DP など水色問題に着手していこうと思います。ただし、まめにバチャに出るなどして、適正難易度の問題に対する感覚を維持することも忘れないよう > 自分