# ABC360 振り返り
- [ユニークビジョンプログラミングコンテスト2024 夏（AtCoder Beginner Contest 359） - AtCoder](https://atcoder.jp/contests/abc359)
- ABCDE 5完 (1381) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc360)
![[スクリーンショット 2024-07-01 8.20.39.png]]
ABC360 でした。
~~B問題のテストに問題があったようで、7/2 AM 6:00 の時点でまだスコアが確定していません。~~ <ins>確定しました。Unrated にはならずに済みました</ins>
- A ··· `R` と `M` のインデックス値の大小関係を比較する
- B ··· ややこしい問題で手こずった人も多かったようです。`chunksOf` と `transpose` で実装すると楽でした
- C ··· 箱 $A_i$ ごとに、その箱に入っている重さ $W_i$ をまとめて、一番大きいもの以外の総計を取る
- D ··· 左向いてるアリと右向いてるアリを分離。右向きを固定して、左向きの中に $2X_i + T$ にいるアリを二分探索
- E ··· 期待値計算を $K$ 回遷移。$N$ が大きいが、ただの定数として扱うように立式できる
E が解けたのはややまぐれみたいなところはありつつ、序盤からスムーズに E までいけて、良かったと思います。
D の 2ペナは、ちょっともったいなかったですが。
## [A - A Healthy Breakfast](https://atcoder.jp/contests/abc360/tasks/abc360_a)
文字列比較や正規表現など、いろんな解き方がありそうです。
自分は素直にインデックスの比較で解きました。
```haskell
main :: IO ()
main = do
s <- getLine
let r = elemIndex 'R' s
m = elemIndex 'M' s
printYn $ r < m
```
## [B - Vertical Reading](https://atcoder.jp/contests/abc360/tasks/abc360_b)
問題文の読解からしてすこしややこしい問題。
`atcoder` という文字列を、例えば $3$ 文字で区切ると `atc` `ode` `r` となりますが、この $3$ つの塊からそれぞれ同じ位置の文字をとる、つまり
```
atc
ode
r
```
をいわゆる「縦読み」すると `aor` `td` `ce` という文字列が得られます。なお問題タイトルは「Vertical Reading (縦読み)」です。
縦読みで作れる文字列を全部作って、その中に $T$ が含まれるか判定せよ、ということです。
Haskell での実装ですが、文字列を任意のサイズの塊に分けるのは `chunksOf` を使う。縦読みには `transpose` を使う。
この二つを組み合わせると綺麗に実装できました。
沼りそうだなー、嫌だなーと思っているところ`transpose` で縦読みすればいいと気づいてほっと胸を撫で下ろしました。
```haskell
main :: IO ()
main = do
(s, t) <- auto @(String, String)
let w = length s
let ss = Set.fromList $ concat [transpose $ chunksOf i s | i <- [1 .. w - 1]]
printYn $ Set.member t ss
```
## [C - Move It](https://atcoder.jp/contests/abc360/tasks/abc360_c)
C 問題にしては比較的簡単です。特定の箱には一つしか荷物を残すことができない。
かつ、荷物をどかすには重さ分のコストがかかる。コストの総和を最小化したい。
箱毎に荷物をまとめて、その中で一番大きい物以外は移動することになります。
移動する荷物は空いてる箱に一つずつ入れていけばよく、同じ荷物を繰り返し移動する必要はなさそう。
荷物を箱ごとにまとめて素直に計算する。
特定の値をキーに結合するので `accumArray` の出番です。が、下界上界の確認が面倒だったので拙作の `accumIntMap` で処理しました。
```haskell
main :: IO ()
main = do
n <- getInts
as <- getInts
ws <- getInts
let xs = zip as ws
g = IM.map sort' $ accumIntMap (flip (:)) [] xs
print $ sum $ IM.map (\vs -> let k = length vs in sum $ take (k - 1) vs) g
```
## [D - Ghost Ants](https://atcoder.jp/contests/abc360/tasks/abc360_d)
数直線上に左を向いている蟻と右を向いている蟻がいて、どの蟻も同じ速度で移動する。$T + 0.1$ 秒後にすれ違う蟻の組数を求める。
右を向いている蟻からすると (後ろから追い越されたりすることはないので) 左を向いている、自分の方に向かってくる蟻にしか関心がない。
お互いが対面で同じ速度を進むので、右を向いてる蟻からすると、相手の蟻との距離は $T$ 秒後には $2 \times T$ 縮まっている。
各右向き蟻の現在地 $X_i$ から、$X_i + 2T$ 以内にいる左向きの蟻が、$T$ 秒後にすれちがう相手です。各右向きの蟻ごとに、すれちがう相手が何匹いるかを数えるとよいでしょう。これを右向き蟻 $i$ の寄与数と考え、二分探索しました。
なお、数列 $X$ がソートされてないのに気づかず 2ペナもらいました 😇
いかにもソート済みそうな顔をした問題なのに、ソートされてないとは。罠です。
```haskell
main :: IO ()
main = do
[n, t] <- getInts
s <- getLine
xs <- getInts
let (right, left) = bimap (map snd) (map snd) $ partition (\(c, _) -> c == '1') $ zip s xs
m = length left
as = listArray @UArray (1, m) $ sort' left
res = [max 0 (boundLE (x + (2 * t)) as - boundLE x as) | x <- right]
print $ sum res
```
### 転倒数でやる
この問題の場合 蟻 $i$ と蟻 $j$ がすれちがう、というのは $X_i$ と $X_j$ の大小が、$T$ 秒後に逆転すると考えることもできます。
系列の中で数字の大小関係が逆転している回数を数える ··· 転倒数が使えます。
$O(N \log N)$ の転倒数の実装を持っているなら、こちらの方が簡単です。
$0.1$ 秒を整数でも正しく計算するために $10$ 倍スケールにして計算します。
左向きの蟻は負の方向に、右向きの蟻は正の方向に実際に進める。その写像された系列の転倒数を求めます。
```haskell
main :: IO ()
main = do
[n, t] <- getInts
s <- getLine
xs <- getInts
let xs' =
[ if si == '1' then 10 * xi + 10 * t + 1 else 10 * xi - 10 * t - 1
| (si, xi) <- sortOn' snd $ zip s xs
]
print $ countInversion xs'
```
### Double でもいける
なお、Double でも通りました。遅いし、危なっかしいのでいずれにせよ整数に変換するほうが良いと思います。
```haskell
main :: IO ()
main = do
[n, t] <- getInts
s <- getLine
xs <- map (read @Double) . words <
gt; getLine
let xs' =
[ if si == '1' then xi + fromIntegral t + 0.1 else xi - fromIntegral t - 0.1
| (si, xi) <- sortOn' snd $ zip s xs
]
print $ countInversion xs'
```
## [E - Random Swaps of Balls](https://atcoder.jp/contests/abc360/tasks/abc360_e)
いかにも期待値DP の顔をした問題ですが、$1 \leq N \leq 998244352$ と $N$ が大きい。
いつものように $0 \ldots N$ の DP配列を用意して...だとうまくいきません。
一方、この問題は操作回数が $K$ 回です。$K$ 回状態遷移を繰り返すことを考えます。
ボールが局面局面でどの位置にあるかを管理するのは $N$ が大きく難しいので、$N$ をただの定数と捉えて、期待値がどう遷移するか数式を立てる方針でやりました。
ボールの選び方は $N \times (N - 1)$ 通り。あとは
- 黒いボールが別の位置に移動しないケース
- 黒いボールが別の位置に移動するケース
それぞれの寄与が、$N$ をもとに計算できれば良さそう。
結論、現在の期待値を $acc$ としたとき
$acc' = \frac{acc \times (N - 1) \times (N - 2) + (1 + N) \times (N - 1)} {N \times (N - 1)}$
となりました。
- 黒いボールが別の位置に移動しないケース
- $1$ 個目が黒いボール以外なので $N - 1$ 個から選択
- $2$ 個目も白いボールなので $N - 2$ から選択
- 現在の期待値を $acc$ とすると $acc \times (N - 1) \times (N - 2)$ が黒いボールが動かない場合の寄与
- 黒いボールが別の位置に移動するケース
- $(1 + N) \times (N - 1)$ が、黒いボールが他の任意の位置に移動する場合の寄与
- $(1 + N)$ ··· $1$ は黒いボールが元の位置に戻る場合の寄与。$N$ は移動する可能性のある位置の数
- $(N - 1)$ は白いボールの個数
- 確率の重みを考慮するため $\frac{1}{N \times (N - 1)}$ する
が詳細です。
先に結論から書いてるので「すわ! 数式で立式!!」という感じにみえますが、実際にはコードを先に実装して式をあれこれいじっているうちにサンプルが全て AC になったので、そのままゴリ押しで通しました。
期待値を「確率によって重み付けした平均値」と捉えて、黒いボールは移動後にだいたいどの辺にあるか、みたいなことを考えながら式をいじっていたのが功を奏したようです。
$N = 1$ のときに逆元 mod の計算がランタイムエラーになるのに気づかず 3回 RE を出しましたが、コーナーケース回避のワークアラウンドを入れて通しました。
```haskell
main :: IO ()
main = do
[n, k] <- getInts
if n == 1
then print 1
else do
let n' = toIntMod n
p = invIntMod (n' * (n' - 1))
let IntMod ans = foldl' f (IntMod 1) [1 .. k]
where
f acc _ =
let acc' = acc * (n' - 1) * (n' - 2) + (1 + n') * (n' - 1)
in acc' * p
print ans
```
## 感想など
久々に水色パフォーマンスが取れて気分は上々、なのですが Unrated になる可能性もあるようで 😅
まあ、そのときはしょうがないですね。
B 問題で沼りそうな実装を避けて `transpose` で実装する、というのを落ち着いて選択できたのがすべてだったような気がします。
あそこで躓いていたら、後半崩れて、E 問題で試行錯誤する時間が取れなかったのではないかと思います。
日々の精進の方は PAST の過去問を、高難易度以外終わらせてしまったので、未AC だった水色上位の問題を解いていってます。
これだけだと本番を想定した実装力が鍛えられないので、そこに ADT をたまに加えるなどしてバランスよくやってます。
おかげさまで実装力はだいぶ安定してきました。
次回 ABC361 は私用のためお休みの予定です。
### 追記
スコアが確定、Unrated にはならず +35 でレートは 1108 になりました。
1100 台になり、目標の水色まであと 92 です。が、ここからが長そうです 😉
![[スクリーンショット 2024-07-05 9.17.25.png]]