# ABC378 振り返り
- [AtCoder Beginner Contest 378 - AtCoder](https://atcoder.jp/contests/abc378)
- ABCDE 5完 (1289) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc378)
![[スクリーンショット 2024-11-04 17.37.38.png]]
ABC378 でした。
E 問題を時間ぎりぎりで通して 5完で、水色パフォーマンスでした。
E が結構難しかったのでもう少しスコアは高くなるかと思いましたが、E を飛ばして F を解いた人も多かったようでこのスコアでしょうか。
- A (灰) ··· 各値の出現頻度 / 2 を足す
- B (灰) ··· $d_i$ からあと何日経過したら余りが $r_i$ になるか、を立式する
- C (灰) ··· $A_i$ が以前にでた出現位置を IntMap に記録しながら写像
- D (茶)··· DFS で経路を全探索。数え上げるだけで OK
- E (水) ··· $A$ の累積和 $s$ をとり $(s_i - s_j) \mod M$ にフォーカスしながら主客転倒。$s_i \geq s_j$ で場合わけすることで、セグメント木があれば計算できる
## [A - Pairing](https://atcoder.jp/contests/abc378/tasks/abc378_a)
数の出現頻度を数えて $2$ で割る。
値が 4つしかないけど、値が $10^5$ とかあっても同じ実装で OK。
```haskell
main :: IO ()
main = do
as <- getInts
let bucket = IM.fromListWith (+) $ map (,1 :: Int) as
print $ sum' [x `div` 2 | x <- IM.elems bucket]
```
## [B - Garbage Collection](https://atcoder.jp/contests/abc378/tasks/abc378_b)
結構ややこしい。
$d_i$ からあと何日経過したら余りが $r_i$ になるか? を計算する。
$d_i - r_i$ で、余分な日数がわかる。これを $q_i$ から引いて $\bmod{q_i}$ をとると $q_i$ で割ったときに余りが $r_i$ になるタイミングが分かる。
実際には適当に立式していじってたらサンプルがあったので、それで送信して通しました。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- replicateM n getTuple
q <- getInt
qs <- replicateM q getTuple
let xa = listArray @Array (1, n) xs
for_ qs $ \(ti, di) -> do
let (qi, ri) = xa ! ti
ans = di + (qi - (di - ri)) `mod` qi
print ans
```
## [C - Repeating](https://atcoder.jp/contests/abc378/tasks/abc378_c)
各 $A_i$ が前回出現した位置を記憶しながら、写像していけばよい。
IntMap で $A_i$ をキーにして管理する。これが状態になる写像なので `mapAccumL` で記述。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let (_, res) = mapAccumL f IM.empty (indexed 1 as)
where
f ix (i, ai) =
( IM.insert ai i ix,
fromMaybe (-1) $ IM.lookup ai ix
)
printList res
```
## [D - Count Simple Paths](https://atcoder.jp/contests/abc378/tasks/abc378_d)
$H, W \leq 10$ 程度と盤面がかなり狭いので、全探索でよい。
経路を全部みつける、となると DFS 。そしてこの問題では実際にどの経路を進んだかのパスには関心がない。
ステップが $K$ になったタイミングでカウントアップ、さえできればよい。
DFS しながら数え上げ、というときは State モナドを使って命令的に書くと、再帰の戻り値のことを気にしなくてよいので楽。
ただし、グローバル変数を書き換え可能な他の言語ならもっと簡単なのになーと思いつつ。
Haskell での実装にやや頭を使う問題。
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)]
dfs' ix k grid visited acc v
| acc == k = modify' (+ 1)
| otherwise = do
for_ lrud $ \d -> do
let u = v + d
when (inRange (bounds grid) u && grid ! u == '.' && IS.notMember (ix u) visited) $ do
dfs' ix k grid (IS.insert (ix u) visited) (acc + 1) u
main :: IO ()
main = do
[h, w, k] <- getInts
grid <- getCharGrid ((1, 1), (h, w))
let vs = findArrayIndices (== '.') grid
ix = index (bounds grid)
res = [execState (dfs' ix k grid (IS.singleton (ix v)) 0 v) (0 :: Int) | v <- vs]
print $ sum' res
```
## [E - Mod Sigma Problem](https://atcoder.jp/contests/abc378/tasks/abc378_e)
$\sum\sum$ の問題なので、例によってナイーブには計算できない。主客転倒する。
$1 \leq M \leq 2 \times 10^5$ というのがいかにも怪しい。
$(A_1 + \ldots + A_N) \mod M$ した結果を、配列なりセグメント木なりに収めることができることを意味している。これを利用する。
$(A_1 + \ldots + A_N) \mod M$ は何かといえば、累積和の $\bmod M$ なので、$A$ の累積和 $s$ に対して $(s_i - s_j) \mod M$ であり、
同じ $(s_i - s_j) \mod M$ が何回出てくるかを計算できれば、答えがそこからが求められそう。
ここで $(s_i - s_j) \bmod M$ を考えたとき、仮に $s_i \geq s_j$ なら $\bmod M$ が取れて
$(s_i - s_j) \bmod M = s_i - s_j$
にして構わない。一方 $s_i < s_j$ の場合、$M$ の分一周することを考えると
$(s_i - s_j) \bmod M = s_i - s_j + M$
とすることができる。
累積和 $s$ を左から見ていきながら $s_i$ と同じ値が過去何回出現して、累計で幾つになったかをセグメント木でそれぞれ管理する。
これによりある $s_i$ を $x$ としたときこれまで出現した $s_j \leq x$ の個数、$s_j \leq x$ の総和が対数時間で求められるようになる。
これは $1 \leq M \leq 2 \times 10^5$ という制約と、動的にそれを管理していく必要がありそうな気配からセグメント木を持ち出せばいいのでは? と当てにいった。
もとい、これで道具は揃う。ある $s_i$ を固定したとき
$s_i \geq s_j$ のケース
$\sum_{j<i}{(s_i - sj)}$
$= (s_i - s_1) + (s_i - s_2) + \ldots + (s_i - s_j)$
$= s_i \times s_jの個数 - \sum s_j$
となって、$s_j$ の出現回数や総計がわかればいいことになる。
$s_i < s_j$ のケースは同様に
$\sum(s_i - s_j + M)$
$= (s_i + M) \times {s_j の個数} - \sum{s_j}$
となる。この $s_i < s_j$ のときの個数や $\sum s_j$ は、先のセグメント木があれば、$s_i \geq s_j$ のケースの余事象として計算できる。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
let s = listArray @UArray (0, n) $ scanl' f 0 as
where
f acc a = (acc + a) `mod` m
counts <- newST @IOUArray (+) (0 :: Int) (0, m - 1)
sums <- newST @IOUArray (+) (0 :: Int) (0, m - 1)
res <- for [0 .. n] $ \i -> do
let x = s ! i
a <- rangeQueryST counts 0 (x + 1)
b <- rangeQueryST sums 0 (x + 1)
totalCnt <- rangeQueryST counts 0 m
totalSum <- rangeQueryST sums 0 m
let s1 = x * a - b
s2 = (x + m) * (totalCnt - a) - (totalSum - b)
updateST counts x (+ 1)
updateST sums x (+ x)
return $ s1 + s2
print $ sum' res
```
## 感想など
今回も考察をしっかりやる、という意識で取り組んでまずますの成績でした。
E を解いたときは、もっとスコアが上がるかなーと思いましたが 4完早解きの人と大してスコアがかわらなかったのは、やや肩透かしではありましたが
まあ、E は $M$ の値の制約をみて「セグメント木かなー」と当てにいって当たったというのが大きく、やや運もあるかなと思いました。
レートは 1138 となり、Highest の 1140 近くまで戻しました。
このまま安定的に水色パフォーマンスを出し続けられれば、入水できそうですがそうは問屋が卸さないのが AtCoder ... 引き続きがんばります。