# ABC351 振り返り
- [AtCoder Beginner Contest 351 - AtCoder](https://atcoder.jp/contests/abc351)
- ABCDF 5完 (1465) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc351)
![[スクリーンショット 2024-04-28 11.40.07.png]]
![[スクリーンショット 2024-04-28 11.40.47.png]]
ABC351 でした。
E は解けませんでしたが、同じ配点の F を解いてパフォーマンス 1465。結果は良かったです。
E は時間的に最後を詰め切れず、初の 6完はなりませんでした。
- A (灰) ··· 2チームの得点の合計をそれぞれ出して、差を出す
- B (灰) ··· 二つのグリッドの同じマスを全探索
- C (灰) ··· ボールをスタックに積み、直前に積んだのと同じのが来たら結合。この結合は再帰的に繰り返す。計算量は問題なし
- D (緑) ··· 磁石の影響のあるマスを最初に `*` などに置換。`.` の連結成分を Union-Find で求めて、成分ごとに周辺の `*` を足す
- E (青, upsolve) ··· 座標を 45度回転して $x$ と $y$ を独立で計算すると楽。$\sum\sum|x_j - x_i|$ はソートして絶対値を外して寄与数で考える
- F (水) ··· BIT を2つ用意して数列の $A$ の後ろから、その時点で $A_i$ より大きい値とその個数をそれぞれ計算。座標圧縮がいる
でした。
D の配点が 425 点といつもより高め。配点通りやや難易度高めで、考察に時間がかかりました。
E と F は配点がいずれも 500点でしたが、その時点の順位表をみて、上位勢が先にみんな F を通していたので私も F にいきました。
この選択は良かったと思います。
## [A - The bottom of the ninth](https://atcoder.jp/contests/abc351/tasks/abc351_a)
9回裏の攻撃で、あと何点勝てるか?
2チームの合計得点を計算して差をとります。
問題をよく読んだら、後攻が既に勝ってるケースは考えなくて良かったですね。
```haskell
main :: IO ()
main = do
as <- getInts
bs <- getInts
let a = sum as
b = sum bs
print $ if b > a then 0 else a - b + 1
```
## [B - Spot the Difference](https://atcoder.jp/contests/abc351/tasks/abc351_b)
二つのグリッドにおいて、一箇所だけ値が違ってるところの座標を探す。
素直に全マスを探索して違うところを見つけました。
```haskell
main :: IO ()
main = do
n <- getInt
gridA <- getCharGrid ((1, 1), (n, n))
gridB <- getCharGrid ((1, 1), (n, n))
let res = [v | v <- range (bounds gridA), gridA ! v /= gridB ! v]
printTuple $ head res
```
## [C - Merge the balls](https://atcoder.jp/contests/abc351/tasks/abc351_c)
ボールを列にならべていくが、一つ前に入れたボールと次に入れるボールの大きさ $A_i$ が同じなら二つを合体させて $A_i + 1$ にする。
その $A_i + 1$ にした結果、さらに一つ前と大きさが合致するならそれも合体させて... を繰り返す。
最後に列に残ったボールの個数を出力する。
```
2 1
```
とあるところに 1 が来たら
```
2 1 1 -> 2 2 -> 3
```
になるみたいな動きですね。
スタックにボールを一つずつ積み、その都度、直前に入れたボールと比較し結合するかそのままにするかを判断します。
この関数を $f$ とします。
もし大きさが同じなら再帰的に $f$ を適用する。これでうまくいきます。
計算量が少し気になるところですが、スタックに入れたボールは結合のたびに数が減るため、$A$ の数 $N$ に対して結合の再帰が $N$ 回走って $O(N^2)$ になるということは起きず、$O(N)$ に収まります。
なお「ボールの大きさは $2^{A_i}$ 」という設定で少し戸惑いましたが、要するに整数が同じかどうかを判断すれば良いだけでした。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let stack' = foldl' f [] as
where
f [] a = [a]
f (x : xs) a
| x == a = f xs (a + 1)
| otherwise = a : x : xs
print $ length stack'
```
## [D - Grid and Magnet](https://atcoder.jp/contests/abc351/tasks/abc351_d)
グリッドをグラフとして考える問題。
`#` は磁石で、その四方に磁場を作る。磁場には進入はできるが、入るとそこから先には進めない。
このグリッド内で移動を繰り返すと最大で何マスに到達できますか? という問題。
入ることはできるがそこで次に進めなくなる、という設定のグリッドは珍しいですね。
で、最初は単純な BFS ··· 磁場に入ったらそれ以上遷移できないようにして探索かな? と思いましたが、
この問題はスタート地点が指定されていません。全マスごとに BFS すると $1000 \times 1000$ マスあるので TLE します。
BFS を全マスごとにやるのではなく、BFS するたびに訪問できた頂点は潰していって、
残ったところから再度 BFS するという方法が考えられます。[kyopro_friends さんの解説](https://x.com/kyopro_friends/status/1784219334627492201) にもありました。
これは思いついたのですが、BFS の結果を格納する配列を使い回しつつ、訪問済みでない頂点からは再度訪問可能...
みたいなことをやろうとすると BFS の盆栽を改造する必要があり、手間取りそうです。
というわけで BFS ではなく Union-Find でやりました。
一見大変そうに見えるかもしれませんが Union-Find なら状態を持たずに計算できるので、🧠 への負荷はそれほどでもないです。
入力例 1 のグリッドを例にとります。
```
.#...
.....
.#..#
```
磁石の影響がある磁場を `.` から `*` に置換します。
```
*#*..
.*..*
*#**#
```
`.` をグラフの頂点みなすと、連結成分数が $1$ と $4$ の成分が二つあります。
それぞれの連結成分の周辺にある磁場にも進入はできるので、連結成分ごとに周辺 `*` の個数も足していけばよいです。
`.` ごとに頂点番号を振る必要がありますが、これは座標圧縮を使えば簡単です。
辞書で (索引, 座標) のペアを持つより速いし、楽ですね。
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)]
main :: IO ()
main = do
[h, w] <- getInts
grid <- getCharGrid ((1, 1), (h, w))
-- 磁石の影響のあるマスを * に置換
let updates =
[ [ (u, '*')
| d <- lrud,
let u = v + d,
inRange (bounds grid) u
]
| v <- findArrayIndices (== '#') grid
]
grid' = grid // concat updates
-- '.' の連結成分を求める
let vs = findArrayIndices (== '.') grid'
n = length vs
(rank, ix) = zaatsuRank @Array 1 vs
uf <- newUF @IOUArray (1, n) (-1)
for_ vs $ \v -> do
let us =
[ v + d
| d <- [right, down],
let u = v + d,
inRange (bounds grid) u,
grid' ! u == '.'
]
for_ us $ \u -> unite uf (ix u) (ix v)
cs <- getComponentsUF uf
-- 連結成分ごとにその周辺にある '*' を数えて、自由度を計算する
let res =
[ length vs + length (nubOrd us)
| vs <- [[rank ! i | i <- is] | is <- cs],
let us =
[ u
| v <- vs,
d <- lrud,
let u = v + d,
inRange (bounds grid) u && grid' ! u == '*'
]
]
print $ maximumWithDefault 1 res
```
## [E - Jump Distance Sum](https://atcoder.jp/contests/abc351/tasks/abc351_e) (upsolve)
ウサギは斜め 4方向いずれかに 1 マスしか動けません。
座標平面上で斜め 1 マスに動く、というのは言い換えれば、マンハッタン距離でちょうど 2 になる座標にしか到達できないことを意味します。
サンプル 1 の $(0, 0) → (1, 1) → (0, 2) → (1, 3)$ はマンハッタン距離の目線でみると、いずれも距離 $2$ だけ移動してるのがわかります。
また、$(0, 0)$ から $(5, 6)$ に到達できないのは、$5 + 6 = 11$ で $2$ の倍数になっていないからですね。
仮に $(0, 1)$ にもポイントがあったとすると $(0, 1)$ からは $(5, 6)$ に移動できます。一方、$(0, 0) → (0, 1)$ は駄目です。
つまり座標の $x + y$ の偶奇が同じ座標間は移動できることを意味します。
ので、$x + y$ の偶奇で $P_i$ を2グループに分けます。
そしてマンハッタン距離といえば座標を $45$ 度回転するのが定番です。
$45$ 度回転すると斜めの移動 $1$ 回が縦横の移動 $2$ 回に変換されて、$x$ 軸と $y$ 軸で独立に計算できるようになります。
2 つのグループに分けて、グループ毎に $x$ 方向の移動量の総計と、$y$ 方向の移動量の総計を計算すれば良いことになります。
$x$ 方向の移動量の総計は、グループに含まれる $P_i$ の個数を $M$ としたとき
$\displaystyle \sum_{i = 1}^{M - 1}\sum_{j = i + 1}^{M}|x_j - x_i|$ になります。$y$ 方向も同様です。
この式をどう計算するかですが実は全く同じ問題が [ABC186 D - Sum of difference](https://atcoder.jp/contests/abc186/tasks/abc186_d) で出題されています。
絶対値を外すためにソートして、寄与数で考えると式が整理できます。
というわけで
- $x + y$ の偶奇でポイントを二つのグループに分ける
- 座標を 45度回転する
- グループごとに $x$ の移動量、$y$ の移動量をそれぞれ ABC186 D の要領で計算する
- 合計して $2$ で割る (マンハッタン距離だとウサギの斜め移動1 回に対して2 かかってるので)
でファイナルアンサーです。
これは本番で解きたかったですね。
あと15分余裕があればいけたような気がします。時間間際に焦ってゴチャゴチャになっちゃいました。
```haskell
f as = do
let n = length as
as' = sortOn' Down as
res = [a * (n - i - 1) + (-a * i) | (i, a) <- indexed 0 as']
sum res
resolve vs = do
let (xs, ys) = unzip vs
f xs + f ys
main :: IO ()
main = do
n <- getInt
vs <- replicateM n getTuple
let (vs1, vs2) = partition (\(i, j) -> even (i + j)) vs
vs1' = map (\(x, y) -> (x + y, x - y)) vs1
vs2' = map (\(x, y) -> (x + y, x - y)) vs2
a = resolve vs1'
b = resolve vs2'
print $ (a + b) `div` 2
```
## [F - Double Sum](https://atcoder.jp/contests/abc351/tasks/abc351_f)
数列 $A$ が与えられて
$\displaystyle \sum_{i-1}^{N}\sum_{j=i+1}^{N}\max(A_j - A_i, 0)$
を求める問題。E 問題に続き、また $\sum\sum$ の計算ですね。
$\sum\sum$ の計算はナイーブにやると間に合わないのですが、寄与数で考えると整理しやすいことが多いですね。
サンプル 1 で考えると
$A_1 = 2$ ··· $A_1$ より右にある $2$ より大きな数は $3$ と $5$ の $2$ 個。その総和は $8$ になる。よって $A_1$ の寄与数は $8 - 2 \times 2 = 4$
$A_2 = 5$ ··· $A_2$ より右にある $5$ より大きな数はない。よって $A_2$ の寄与数は $0$
$A_3 = 3$ ··· $A_3$ より右にある $3$ より大きな数はない。よって $A_3$ の寄与数は $0$
となります。$A$ の個数が増えていっても考え方は同じです。
- 自分より右側にいくつ、自分より大きな数があるか?
- 自分より右側の自分より大きな数の総和はいくつか?
この二つがわかれば寄与数の計算が可能なことがわかります。
こういう、ある局面で自分より大きな数が何個あるか、とか自分より大きな数の総和がいくつか? というのはセグメント木や Binary Indexed Tree (Fenwick Tree) 、つまり一点更新区間和を得意とするデータ構造があれば計算できます。
最近出た問題だと [ABC331 C - Sum of Numbers Greater Than Me](https://atcoder.jp/contests/abc331/tasks/abc331_c) が「$A$ の要素のうち $A_i$ より大きな要素全ての和を求めよ」という問題ですね。
左から数列をみていって、セグメント木もしくは BIT の $i = A_i$ に $A_i$ を一点更新で加えてくと、区間 $[A_i + 1, N)$ の和で $A_i$ より大きな要素すべての総和が求まります。
これを応用することで解けます。
知りたいのは $A_i$ より大きな数の個数、総和の二種類なので BIT を二つ用意します
$A_i$ より右側に位置する整数に対して調べたいわけですが、ABC331 C のように BIT を構築しきってからの区間和だと「右側に位置する」というのがうまく計算できません。左側にあるものまで巻き込んでしまいます。
ちょっと工夫して、後ろからみていきます。後ろから BIT に追加していって $A_i$ が来た時点で $[A_i, N)$ の区間和をとると、まだ左側の要素は BIT に含まれていないので、$A_i$ から右側にある要素のうち $A_i$ より大きな値全ての個数 / 総和が計算できます。
この、BIT を更新する過程で区間取得を行うという方法は [ABC276 F - Double Chance](https://atcoder.jp/contests/abc276/tasks/abc276_f) で学びました。
こういうの平面走査というんですかね? (よくわかってない)
もう一点。この問題では $A_i$ が $10^8$ くらいの大きさになるので、そのままでは BIT の索引として扱えません。
というわけで D 問題に続きここでもまた座標圧縮します。
わーわー書いてますが実装にすると意外とあっさりです。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let (rank, ix) = zaatsuRank @UArray 1 as
n' = numElements rank
counts <- newBIT @IOUArray @Int (1, n')
sums <- newBIT @IOUArray @Int (1, n')
res <- for (reverse as) $ \a -> do
let i = ix a
k <- rangeSumBIT counts (i + 1) (n' + 1)
s <- rangeSumBIT sums (i + 1) (n' + 1)
incrementBIT counts i 1
incrementBIT sums i a
return (a, k, s)
let res' = [s - a * k | (a, k, s) <- res]
print $ sum res'
```
## 感想など
前回、今回とで水色パフォーマンスをとることができて、レートが 1099 の Highest になりました。
前々回まで負け続けていたので、素直に嬉しいです。
一時期 ADT Medium を毎日やり続けていて、おかげで序盤の問題の速度が上がって安定性が向上しました。
今回も A, B, C あたりはスムーズに解けたと思います。
一方、ADT Medium をずっとやっていると、やがて解いたことがある問題ばかり解く日々になってしまい負荷が足りなくなってきました。
この練習法だと解けない問題を延々と考えるみたいな負荷がかかっていないこともあり、本番でもやや難しい問題が出ると
早々に諦めてしまうようなところがありました。
もう少し負荷をかけたほうがいいと思い、ADT Hard と、ABC の過去回のバーチャル参加をやるように切り替えました。
当然、水色後半や青色、ときには黄色の解いたことがない問題が出るのですが
バチャ 1回あたり少なくとも未完 1問は真面目に取り組むようにしてます。
このとき難易度表示の拡張はオフにして最初から諦めてしまわないようにしています。
バチャの時間内に解けなかったらそこで切り上げて upsolve します。
こうして日常的に難易度の高い問題でも (難易度を伏せて) 取り組んでいると、
思考の粘り強さが鍛えられるというのはあると思いました。
未完の高難度問題ばかりやっていると upsolve ばかりで何より面白くないので、
その意味でもバチャで前半の問題を無双して、仕上げに1、2問やるというリズムは悪くないです。
時間制限があって集中できることと、時間がすぎたら切り上げて upsolve、と割り切れるところもよいですね。
次回 5/4 の ABC352 もこの調子でいきたいところですが、私用のため一回休みです。