# ABC357 振り返り
- [サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357） - AtCoder](https://atcoder.jp/contests/abc357)
- ABCD 4完 (1012) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc357)
![[スクリーンショット 2024-06-09 11.21.49.png]]
ABC357 でした。
C は Haskell で素直に書くと再帰になるわけですが、ちょっと手間取ってしまい結果は 4完止まり。
E は時間が実質 10分ぐらいしかなく、AC できず。
- A (灰) ··· 累積的に計算していって $M$ を使い切るところまでの件数を数える
- B (灰) ··· 問題文どおりにシミュレーション。 Haskell なら `isAsciiUpper` `isAsciiLower` `toUpper` `toLower` を使う
- C (灰) ··· ブロックを再帰的に生成する
- D (緑) ··· 等比級数の和。オーバーフローが怖い
- E (水, upsolve) ··· SCC して BFS
でした。
C が灰色 diff なのが、ちょっと意外です。もしかして手続き型言語ならもっと簡単に実装できるのかな?
私は C を Haskell らしくイミュータブルな再帰で実装したところ、結構難しく感じました。
今回は難易度的には C > D > E ···というのが自分の感触です。
## [A - Sanitize Hands](https://atcoder.jp/contests/abc357/tasks/abc357_a)
A 問題にしてはいつもより少し難しめですね。B で出てもおかしくないかも。
$M$ から初めて累積で $H_i$ 分引いていって、$M$ の消費履歴を追う。
残り量が $0$ 以上の場合は消毒できたことになるので、その区間の長さを数えれば OK
```haskell
main :: IO ()
main = do
[n, m] <- getInts
hs <- getInts
let res = scanl' (-) m hs
print $ length $ filter (>= 0) (tail res)
```
## [B - Uppercase and Lowercase](https://atcoder.jp/contests/abc357/tasks/abc357_b)
問題文に書かれたとおりにシミュレーションする。
大文字小文字判定や変換は Data.Char にある関数を使えば良いです。
```haskell
solve s
| n > m = map toUpper s
| otherwise = map toLower s
where
n = countBy isAsciiUpper s
m = countBy isAsciiLower s
main :: IO ()
main = do
s <- getLine
putStrLn $ solve s
```
## [C - Sierpinski carpet](https://atcoder.jp/contests/abc357/tasks/abc357_c)
これは沼りました。
レベル $0$ の図形の形は決まっているので、レベル $N$ は再帰的にレベル $N - 1$ の図形を利用して作ります。
レベル $N - 1$ → レベル $N$ の図形は、縦横のサイズが $3$ 倍になります。
その上で、レベル $N$ の図形の各マス $(i, j)$ は、レベル $N - 1$ の図形 $S_{N - 1}$ 縦横サイズが $k$ だとすると $S_{N - 1} (i \mod k, j \mod k)$ になるところがポイントです。実装に夢中になっていてここの整理をするのに時間がかかってしまいました。
紙に書くと良いですね。
下記の左上の $3 \times 3$ はレベル $1$ の図形で、そこからレベル $2$ の図形に拡大するときの方針です。
中央の区画を全部空白にする件はいったんおいておいて、$3$ 倍化されたそれぞれの図形のマスはどう埋めるべきか。
赤字で書いているとおり、レベル $1$ の図系が左上にあったとするとそれを周期的に繰り返すだけなので縦横 $\mod k$ を取ることで、レベル $1$ の図景のどの部分を使えばいいかが分かります。
真ん中の区画を空白にするには、座標 $(i, j)$ が真ん中の区画かどうかを判定できればよいです。
これは $\lfloor i / k \rfloor = 1$ かつ $\lfloor j /k \rfloor = 1$ かどうかを調べると、判定できます。
というわけで方針としては
- 再帰でレベル $N - 1$ の図形を手に入れる
- その縦横 $3$ 倍の領域を用意して、周期性を利用して、各マスを埋める
ということをやれば良い。
中央を白抜きにする、というのはありますが改めて考えてみると、グリッド倍化の典型ですね。
倍化してしまってから真ん中をくりぬいて良いので、まずはグリッド倍化。
それに再帰構造が備わっている、という問題だと思いました。
![[IMG_1126.jpeg]]
実装は以下になりました。
`mapFor` は `flip map` して `map` の引数の順序を入れ換えた自作関数です。
```haskell
dfs' :: Int -> [String]
dfs' 0 = ["#"]
dfs' n = do
let s = dfs' (n - 1)
k = length s
k' = k * 3
mapFor [0 .. k' - 1] $ \i ->
mapFor [0 .. k' - 1] $ \j ->
if i `div` k == 1 && j `div` k == 1
then '.'
else s !! (i `mod` k) !! (j `mod` k)
main :: IO ()
main = do
n <- getInt
let res = dfs' n
for_ res putStrLn
```
冷静に紙の上で考察してから実装すればここまで沼らなかったですね。
実装しながら考えていたので、ごちゃついてしまった感があります。
当初、これぐらいならソラでいけるかなーと思って実装してテストを流したら以下の有様で青ざめました 😨
![[スクリーンショット 2024-06-08 21.48.33.png]]
### ixmap を使う
ところで先の実装がやっていることは、二次元のリストを拡大しつつ、拡大後の各マス $(i, j)$ を、拡大前のマスのどこに写像するかを決めていると考えることができます。
Haskell の配列の ixmap が使えそう、ということで ixmap で実装すると以下のようになりました。
ザッツ・シンプルです。
ixmap によるグリッドの倍化
最初からこのモデルに頭がいけばよかったんですが、まだ 🧠 が育っていないようです。
```haskell
f 0 = listArray @UArray ((0, 0), (0, 0)) ['#']
f n =
let grid' = ixmap ((0, 0), (3 * k - 1, 3 * k - 1)) (bimap (`mod` k) (`mod` k)) grid
in grid' // [(v, '.') | v@(i, j) <- indices grid', i `div` k == 1, j `div` k == 1]
where
grid = f (n - 1)
k = 3 ^ (n - 1)
main :: IO ()
main = do
n <- getInt
printCharGrid $ f n
```
## [D - 88888888](https://atcoder.jp/contests/abc357/tasks/abc357_d)
等比級数の和であることに気がつけるかどうか。
適当に $V_{12}$ とかを考えてみます。
$V_{12} = (12, 12, 12 \ldots, 12)$
と $12$ が $12$ 回繰り返します。$12$ が $1$ 回繰り返すたびに $V$ の桁数が、$12$ の桁数である $2$ だけ増加することが分かります。
要するに $N = 12$ という整数を塊にして $10$ 進数みたいに桁上がりしていく構造になっている、ということが分かります。
これが、$N = 3333$ なら繰り返し一回ごとに $4$ 桁分、つまり $10^4$ 増加する。
ところで $10$ 進数は式にすると
$2345 = 5 \times 10^0 + 4 \times 10^1 + 3 \times 10^2 + 2 \times 10^3$
と書けます。構造的にはこれとほぼ同じなので $V_N$ は式にできそう。
$N$ の桁数を $d$ とおくと、この桁数の増加分は $10^d$ と書けて、結果
$V_N = N \times 10^{d \times 0} + N \times 10^{d} + N \times 10^{2d} + \ldots + N \times 10^{(N - 1)d}$
となります。ちょっと見づらいので $10^d = a$ と置き換えます。
$V_N = N \times a^0 + N \times a^1 + N \times a^2 + \ldots + N \times a^{N - 1}$
この式は $N$ でくくることができて
$V_N = N \times (1 + a + a^2 + \ldots a^{N - 1})$
となります。
括弧の中は $a$ 倍ずつ増えていく数の和、等比数列の和ですね。(初項 $1$ 、公比 $a$、項数 $N$ の等比数列の和)
等比数列の和にはお馴染みの公式があるので $O(1)$ で計算可能です。
公式を使って整理すると
$V_N = N \times \frac{a^N - 1}{a - 1} = N \times \frac{10^{dN} - 1}{10^d - 1}$
となります。ここで $d$ や $N$ は入力から全て決まるので、これで計算できます。
注意点が一つあり、$N \times d$ は問題の制約上、整数でやるとオーバーフローします。
mod 998244353 を取りながら、$10^N$ を先に計算してその後 $d$ 乗することでこれを回避できます。
```haskell
main :: IO ()
main = do
s <- getLine
let d = length s
n = stringToInt s
a = ((IntMod 10 ^ n) ^ d) - 1
b = invIntMod $ IntMod 10 ^ d - 1
IntMod ans = toIntMod n * a * b
print ans
```
もしくは多倍長整数を使う。
```haskell
main :: IO ()
main = do
s <- getLine
let d = length s
n = read @Int s
x :: Integer
x = fromIntegral n * fromIntegral d
a = powMod 10 x modulus
a' = toIntMod (a - 1)
b = invIntMod $ IntMod 10 ^ d - 1
IntMod ans = toIntMod n * a' * b
print ans
-- 繰り返し二乗法による累乗 / 法を指定 (Python の pow 相当)
-- ex) powMod 2 60 998244353
powMod :: (Integral a1, Integral a2) => a1 -> a2 -> a1 -> a1
powMod _ 0 _ = 1
powMod x n m
| even n = (t * t) `mod` m
| otherwise = (((x * t) `mod` m) * t) `mod` m
where
t = powMod x (n `div` 2) m
```
オーバーフローのところで 1 WA もらってしまいましたが、この問題は比較的スムーズに解けました。
## [E - Reachability in Functional Graph](https://atcoder.jp/contests/abc357/tasks/abc357_e) (upsolve)
問題のタイトルにもあるとおり、Functional Graph の問題です。
Functional Graph は
- すべての頂点の出次数が $1$ の有向グラフ
- Functional Graph の性質として、$G$ の連結成分が $K$ 個あって $C_1, C_2, \ldots, C_K$ とする。このとき各連結成分には閉路が $1$ つだけ存在する
という性質を持ちます。この問題的には、特に後者が重要です。
この問題の典型的なグラフを図に起こすと以下のようになります。
![[新規ドキュメント 2024-06-09 13.05.45_1.jpg|600]]
グラフ全体は連結しているとは限らないので、いくつかの連結成分に分かれます。
Functional Graph なので、各連結成分は閉路を一つ持ちます。閉路にいない頂点は、その閉路に流れ込んでいく経路に位置することになります。
各頂点の寄与数、つまり各頂点から到達可能な頂点の数を見てみます。
- 閉路にいる頂点は (互いに行き来できる頂点集合が閉路なので) その寄与数は閉路内の頂点数に等しい
- 閉路の外にいる頂点は、閉路から $1$ ホップ離れるたび寄与数が $1$ 増える
となっています。
なお、自己ループを持つ頂点もそれ単体で閉路を成していると見なしてよいです。
ここまで分かればあとは簡単で、
- グラフ全体を SCC (強連結成分分解) して閉路を見つける
- その閉路の頂点の初期コストを、その閉路の頂点数にセットして、そこから有向グラフを逆向きに BFS する
これで全ての頂点の寄与数が求まります。
SCC の盆栽を持っていて、かつ Functional Graph の性質を知っていれば解ける問題だと思いました。
ま、知ってたのに解けなかったんですけどね 😉
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let uvs = indexed 1 as
g = graph (1, n) uvs
g' = invGraph (1, n) uvs
cs <- sccM g
let cs' =
concat
[ [(v, len) | v <- vs]
| vs <- cs,
let len = length vs,
len >= 2 || let u = head vs in g ! u == [u]
]
dist = bfs (g' !) (-1) (bounds g) cs'
print $ sum (elems dist)
```
## 感想など
C で沼らずあと30分もあれば E は解けていたなあと思うと、悔しいところです。
とはいえ C も D も Haskell で実装するのには多少骨が折れるところ、
- C は再帰 + イミュータブルはそもそも書くのが大変
- D はオーバーフローの扱いおよび逆元 mod など
などもあったので、まあそこそこ戦えたかなとは思います。
4回連続、微妙に冷えてレートは横ばいを続けています。
5完、6完でスッキリしたいところですが C や D で沼ってその先に進めないというのがここ数回続いています。
以前のように総崩れになることはなくリカバリして、スコア 1000 前後で踏み留まれているのは上達したんだろうと思っています。
今回の問題セットだと、この 4完でもう少しスコアは良さそうと予想したのですが
やはり全体のレベルが上がっているのでしょうか。思ったよりも低く 1000 ちょっと程度でした。
なんとかここを突破して、1200前後をコンスタントに出せるようになりたいです。
引き続き PAST 過去問を中心に精進を続けます。