# ABC336 振り返り
- [AtCoder Beginner Contest 336 - AtCoder](https://atcoder.jp/contests/abc336)
- 成績 ABC 3完 (942) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc336)
![[スクリーンショット 2024-01-15 19.13.40.png]]
![[スクリーンショット 2024-01-15 19.14.26.png]]
2024年 2回目の ABC、 ABC336 でした。
C まで調子よく解いていましたが、D で失速。80分格闘するも結局 D が解けず。
D を解いていればレート的には水色ぐらいはいけたかなあと思い、悔しいところです。同じく D で詰まった人が大勢だったようで緑パフォーマンスは確保しましたが、C まで灰色難易度だったこともありやや不完全燃焼です。
- A (灰) ··· 文字列操作、やるだけ
- B (灰) ··· 整数を $2$ 進数にして Traling zeros を数える
- C (灰) ··· $N - 1$ を 5進法で解釈する
- D (緑) ··· 両側から考える。$A$ を上界とみなした単調増加列を生成する
- E (水) ··· 桁DP
という感じでした。
----
## [A - Long Loong](https://atcoder.jp/contests/abc336/tasks/abc336_a)
比較的素直なA問題。やるだけです。
```haskell
main :: IO ()
main = do
n <- getInt
putStrLn $ "L" ++ replicate n 'o' ++ "ng"
```
----
## [B - CTZ](https://atcoder.jp/contests/abc336/tasks/abc336_b)
$N$ を 2進数にして後ろから $0$ が続く数を数える。
$N$ 進変換は従前から盆栽してあります。
```haskell
main :: IO ()
main = do
n <- getInt
let xs = takeWhileEnd (== 0) (toDigits 2 n)
print $ length xs
```
----
## [C - Even Digits](https://atcoder.jp/contests/abc336/tasks/abc336_c)
「$n$ を $10$ 進法で表したときに、偶数の数字 $(0,2,4,6,8)$ のみが登場する」とは、すなわち $5$ 個の記号を使って数を表現することです。
5進数として解釈すれば OK。但し $0$ 始まりなので $-1$ する必要があります。
最初 $-1$ するのに気づかず「なんか合わないな」と思ってデバッグしたところ、少しだけずれていたのでピンときました。
```haskell
f 0 = 0
f 1 = 2
f 2 = 4
f 3 = 6
f 4 = 8
f _ = error "invalid"
main :: IO ()
main = do
n <- getInt
let s = map (intToDigit . f) $ toDigits 5 (n - 1)
putStrLn s
```
ちなみに
と、一週間前に投稿していて、まさにこれそのものの問題が出ました。こういうこともありますね。
----
## [D - Pyramid](https://atcoder.jp/contests/abc336/tasks/abc336_d) (upsolve)
苦戦の末解けなかった問題。
- ピラミッドは山の形をしている。左右から山の高さ上限を求めて結合する
- 山の高さは、単調増加する系列に対し $i$ の上界が $A_i$ が決められているときの系列を求める...という考え方で算出する
とすると良かったですが、本番中にはしゃくとり法みたいなことをやったりして沼ってしまいました。
80分かけて解けなかった割りに、実装にするとあっさりです。
```haskell
main :: IO ()
main = do
_ <- getInt
as <- getInts
let left = scanl' (\acc a -> min (acc + 1) a) 0 as
right = scanr (\a acc -> min (acc + 1) a) 0 as
xs = zipWith min (tail left) (init right)
print $ maximum xs
```
左右からみるというのは ABC334 C - Socks 2 のときにも出てきました。
それは比較的思いつき易いと思いますが、その後の $i$ の位置での山の高さをどう決めるか、ここが難しかったです。
この計算は解説をみると DP とあります。ただ、自分のメンタルモデルとしてはあまり DP という感じではないですね。
この計算は何をやっているのだろう...と改めて考察しましたが
- 仮に数列 $A$ の制限がなかったとすると、上界なしで $1, 2, 3, 4, 5 \ldots$ という単調増加列が生成される
- 対して $A$ が、その単調増加列の $i$ の局面で、上界を $A_i$ に抑える役割を果たす
という構造になっています。
`scanl' (\acc a -> min ...)` でやっているのは、この放っておくと単調増加する系列を別途設定された上界で抑えながら生成するという計算になります。
![[IMG_0484.jpeg]]
これとほぼ同じ構造の問題が [ABC263 D - Left Right Operation](https://atcoder.jp/contests/abc263/tasks/abc263_d) として過去に出題されていました。
$i \times L$ が $i$ における上界あるのに対して、数列 $A$ の累積和をとっていきつつその上界で抑える。先の問題に同じですね。
```haskell
main :: IO ()
main = do
[n, l, r] <- getInts
as <- getInts
let left = scanl' (\acc (i, a) -> min (acc + a) (i * l)) 0 (zip [1 ..] as)
right = scanr (\(i, a) acc -> min (acc + a) (i * r)) 0 (zip [n, n - 1 ..] as)
res = zipWith (+) left right
print $ minimum res
```
この ABC263 D は以前に解いているのですが、単調増加列 + 上界、という計算構造になっているとまでは考察しきれておらず。
今回類題を二つならべてみて、こういう計算をしていたんだなということに気がつきました。
----
## [E - Digit Sum Divisible](https://atcoder.jp/contests/abc336/tasks/abc336_e) (upsolve)
桁DP です。問題の構造からして桁DP なのはすぐにわかりますが、解くのには少し工夫が必要でした。
$N$ の最大値である $10^{14}$ に対して桁和の上界は $9 \times 14 = 126$ にしかならない、という点。これをどう利用するかが焦点です。
仮にこの問題が「$N$ 以下の整数の桁和が $s$ であるケースは何回あるか」という問題だとしたら、EDPC の [S - Digit Sum](https://atcoder.jp/contests/dp/tasks/dp_s) にあるような典型的な桁DP になります。つまり桁DP なら桁和が $s$ になる回数の数え上げは簡単です。
この問題では、そこに「 $n$ が $n$ の桁和 $s$ で割り切れるケースは何回あるか?」という捻りが入った問題とみなすことができます。
桁和 $s$ だけでなく $n$ も表現する必要があるのが難所ですね。
一気に解こうとすると難しいですが、以下のように考えるとよいです。
- DP の構成としては、まず簡単なところから考えます 。「$0 \ldots N$ が特定の数 $s$ で割りきれるかどうか」という DP と考えます。これはとても簡単。整数の遷移を $\mod s$ 空間に閉じ込めて、それを DP の次元にして桁 DP すればよいです。
- でもこれだけだと $N$ 以下の整数で「$s$ で割り切れるものの個数」までしかわからない。「桁和が $s$ のとき、かつ $s$ で割り切れている」という解像度で調べられる必要がある。そこで桁和の次元を加えて解像度を上げる。これである特定の $s$ に対して「$N$ 以下の整数の桁和が $s$ のとき、$s$ で割り切れるケースは何回あるか」を求めることができる
- $s$ は特定の値決め打ちなところ、$1 \ldots 126$ まで $126$ 回 DP することで、すべての桁和について計算できる
まとめると、$N$ 以下の整数を $s$ で割り切れるものの個数を求める、という桁DP の典型に一つ工夫として DP の次元を上げて、桁和の解像度を増やす。そして $s = 1 \ldots 126$ まで個別に $126$ 回 DP する、となります。
桁DP は拙作の `accumArrayDP` 関数で実装できます。
```haskell
main :: IO ()
main = do
n <- getLine
let xs = map digitToInt n
let dp s = accumArrayDP @UArray f (+) (0 :: Int) ((False, 0, 0), (True, s - 1, 9 * 14)) [((False, 0, 0), 1)] xs
where
f ((False, i, k), v) x =
((False, (i * 10 + x) `mod` s, k + x), v) :
[((True, (i * 10 + j) `mod` s, k + j), v) | j <- [0 .. x - 1]]
f ((True, i, k), v) _ = [((True, (i * 10 + j) `mod` s, k + j), v) | j <- [0 .. 9]]
print $ sum [dp' ! (False, 0, s) + dp' ! (True, 0, s) | s <- [1 .. 9 * 14], let dp' = dp s]
```
D を「ABC263 D の類題だ!」とシュッと10分ぐらいで解いて、残り 70分をこの桁DP に当てて 5完 ! という流れを脳内で妄想しましたが、そんなにうまくはいきません。
----
## 感想
必死で4完するも茶色パフォーマンスに終わった前回に比較し、開始20分弱で3問解いてあとは椅子を暖めた今回の方がスコアが高いというのは皮肉なものです。
D も E も、理解できればなかなか面白い問題でしたね。
気づけばもう3ヶ月ほどレート 930 〜 990 あたりをうろうろして横ばいです。まあでも、あまりレートを気にしていると本番で変なプレッシャーがかかってしまうので、あくまでコンテストは腕試しの回と位置づけ、レートは後からついてくるものと思っておくことにします。
最近の精進としては
1. ADT 全部やる ··· その週の ADT はバーチャル参加でいいのでその週に全部やる
2. 難易度 1200 〜 1400 のABC 水色 diff 前半解く
3. 水色 diff に疲れたら ARC の灰色、茶色のまだ解いてないの解く
4. ビットごとに独立で考える、二次元累積和、期待値DP、桁DP など苦手領域の問題を集中的に解く
みたいなことをやっています。2 は 105 問中、残り数問まで来ました。
2 の 2週目に入って無双が始まると、そこから過去の記憶が呼び起こされる & 強化されて一気に伸びるフェーズに入れると思います。緑のときもそうでした。がんばります。