# ABC334 振り返り - [ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334) - AtCoder](https://atcoder.jp/contests/abc334) - 成績 AD 2完 (687) [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc334) ![[スクリーンショット 2023-12-24 8.18.41.png]] 2023最後の ABC、 ABC334 でした。 残念ながら有終の美とはいかず、悔しい結果になりました。 今回は B と C の配点がいつもより高いので、序盤の難易度が高いだろうと心の準備はしていましたが、案の定そこで詰まってしまいました 😭 いやあ、まだまだですね。 - A (灰) ··· 大小判定、やるだけ - B (茶) ··· 数直線全体を $-A$ 方向に写像してから考えるとよい - C (緑) ··· $2$ ペアになってるものは無視して良い。与えられた数列 $A$ だけで答えは求まる。両側から累積和 - D (茶) ··· 累積和 + 二分探索 - E (緑) ··· Union-Find して全探索 でした。 本番に解けなかった問題はいつもよりしっかり目に振り返っていきましょう。 ---- ## [A - Christmas Present](https://atcoder.jp/contests/abc334/tasks/abc334_a) これはやるだけ。大小判定。 ```haskell main :: IO () main = do [b, g] <- getInts putStrLn $ if b > g then "Bat" else "Glove" ``` ---- ## [B - Christmas Trees](https://atcoder.jp/contests/abc334/tasks/abc334_b) (upsolve) $A$ を開始位置とした、左右に伸びる等差数列がある。$L, R$ 区間で切り取ったときにそこに何個、要素が入るか。 $A$ が中途半端な位置で始まっていると色々場合分けが必要そうでややこしい。 こういうときは座標自体を写像で動して $A$ を原点にすると考えやすくなります。ええ、本番ではできなかったわけですが。 ![[IMG_0363.jpeg|600]] あとはこの新しい $L, R$ 区間の中に幾つ要素が入るかを考えます。 上記のような、$0$ が $L, R$ 区間に入っているものより以下のような $0$ が外にあるほうが考えやすいのでこちらで考えます。 見てすぐわかるとおり、$R$ までに入っている要素の数から、$L$ までの要素の数を引けば良いですね。 ![[IMG_0364.jpeg|600]] ただし境界部分に注意が必要、$L$ ぴったりと $R$ ぴったりに重なる要素は区間に入ってるとみなす必要があります。 特に $L$ を引くときに $L$ そのものは引いてはいけない。結果 $R / M - (L - 1) / M$ になります。 この式は $0$ の位置がどこにあっても同じです。 例えば前の図のように $L$ が $0$ より左にある場合も、符号が逆転することによって先の式で想定どおりの結果になります。負の符号って凄いですね (中学生並みの感想) ```haskell main :: IO () main = do [a, m, l, r] <- getInts let l' = l - a r' = r - a print $ r' `div` m - (l' - 1) `div` m ``` ---- ## [C - Socks 2](https://atcoder.jp/contests/abc334/tasks/abc334_c) (upsolve) $2$つで $1$ ペアの靴下 $N$ 個のうち、$K$ 個はペアの片方がなくなっていてペアを作りなおすが、より近い位置にある要素同士でペアを組んだほうがよい、という条件のもとどうペアを組めば良いか。ペアの位置が遠いとペナルティが増える。 まず、シミュレーションしてみると $2$ つ残っている正常な靴下は無視してよいことがわかります。 その正常な靴下の一方を、なくなっている一方と組み合わせたところで全体のスコアには影響がありません。正常な靴下から一つ使ってしまうとそれがまた異常な要素になってしまい、結局差し引きゼロです。 すると ``` 1 2 4 7 8 ``` と単調増加する数列があったときに、明らかに位置が近いもの同士でペアにすればよい、という問題に帰着します。 上記でいうと $4$ を取り除いて先頭からペアリングすれば最適解になります。要素数が偶数のときはそもそもそれも考える必要がなく単に先頭からペアリングするだけ。 これが簡単そうで意外と解けない。 結論としては、$10^5$ 個ある要素から $1$ つだけ取り除くときの典型である、左右から演算する、でした。 この問題の場合は、左からペアを作る、右からペアを作る。実際のスコアを $| i - j |$ としてその累積和をとる。 それを重ね合わせることで、どこを取り除けば最適化がわかります。 左右から、というのは一度思いついたのですが累積和と組み合わせる発想に至らずでした。 ```haskell solve n k as | even (2 * n - k) = sum $ map (\[a, b] -> b - a) $ chunksOf 2 as | otherwise = do let prefixSum = scanl' (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (init as) suffixSum = scanr (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (tail as) minimumWithDefault 0 $ zipWith (+) prefixSum suffixSum main :: IO () main = do [n, k] <- getInts as <- getInts print $ solve n k as ``` ## Prefix sum / Suffix Sum ところで「累積和」は英語で "cumulative sum" ですが、別名 "Prefix sum" です。 > 「Prefix Sum」（累積和）がその名前で呼ばれる理由は、このアルゴリズムが配列の各要素に対して、その要素の「前置き（prefix）」すなわち、配列の始めからその要素までのすべての要素の和を計算するからです。 ChatGPT 先生より。 今回の問題の後ろからの累積和は「Suffix sum」と言えますね。 前から累積する、後ろから累積する。累積和を日頃から Prefix Sum と呼んでいれば、それに対応する Suffix Sum を使うというのを自然と思いつけるかもしれません。今後は意識的に `prefixSum` や `ps`という変数名を使ってみようと思います。 ---- ## [D - Reindeer and Sleigh](https://atcoder.jp/contests/abc334/tasks/abc334_d) B と C で頭がごちゃごちゃになったところに、まるで実家に戻ったかのような安心感のある問題。 Prefix Sum ··· 早速使います ··· を先頭から二分探索して $X$ を超える箇所に境界を引く。 これを C 問題にしてほしかった 😂 ```haskell main :: IO () main = do [n, q] <- getInts rs <- getInts qs <- replicateM q getInt let prefixSum = listArray @UArray (1, n + 1) $ scanl' (+) 0 (sort rs) for_ qs $ \query -> do let (ok, _) = bisect2 (0, n + 2) (\i -> prefixSum ! i <= query) print $ max 0 (ok - 1) ``` ---- ## [E - Christmas Color Grid 1](https://atcoder.jp/contests/abc334/tasks/abc334_e) (upsolve) D を解いたところで、解けそうで解けてない C に戻るか E にいくか迷いましたが、C に行きました。 この判断は結論、間違いでしたね。冷静に考えれば E の方が配点が高いわけですし、こちらを優先すべきでした。 さて、正直にいうと B, C よりもこの E の方が簡単でした。 グリッド上に `#` が置かれたマスを頂点とみなし上下左右にある `#` とは隣接するグラフがある。 そこに新しく `#` を一つ入れると、グリッドの連結成分数はどう変動するか? 最終的には期待値を求めますが、そこは本筋ではないです。 以下のグリッドは連結成分の個数が $2$ です。 ``` ##. #.# #.. ``` 一つ `#` を入れます。右上に入れてみます。 すると全て連結になるので、連結成分の個数は $1$ になります。 ``` 3 3 ### #.# #.. ``` 変わって右下にいれてみると、この場合は元々あったグラフは連結しないので、連結成分数は減りません。 ``` ##. #.# #.# ``` これを全ての `.` に対して考える必要があります。 連結成分の数を少ない計算量で求められる実装がほしい。となると Union-Find ですね。 - 先に全体の Union-Find を作って、連結成分の個数を求めておく - `.` のマスを全探索して、ある `.` を `#` に変更したときその前後で連結成分数がどう変化するかを計算する とします。後者をどうするか? このときある `.` が `#` に変化するとき、その影響を受けるのは周囲 $4$ マスのごく小さな範囲だけです。そこだけに絞って考えます。 ``` # #.# # ``` 名前で呼びやすいように以下のように $A, B, C, D, X$ にします。 ``` A BXC D ``` $X$ を `#` にすると、結果的には $A, B, C, D$ すべてがそれによって連結になります。結局、この小さなグリッド自体は連結成分が $1$ になります。 `#` を入れる前は $A, B, C, D$ だけで考えれば例えば上図では連結成分 $4$ なわけですが、実際には、例えば $A$ と $C$ がこの範囲外ですでに繋がってる可能性もあるのでそう単純ではないです。 裏を返せば、範囲外で繋がっていることがわかればそこは既に連結済みと考えればよいわけですね。 先に全体の Union-Find を作っているので、それを使って調べることができます。 結局、`.` を全探索をして各々周囲 $4$ マスをみる。そこに `#` がある場合、それらの連結性を調べてその段階で連結成分が幾つになっているかを算出する。`.` を `#` にすることでその連結成分が $1$ になる。この前後が `#` をいれたことにより発生した差ですね。 小さなグリッドの前後の差をどう取るかですが、私は頂点数 $5$ 個の小さな Union-Find を作って、全体の Union-Find の連結状況をそこに写し取り、その後 `#` を真ん中に加える... という方法で計算しました。 ```haskell main :: IO () main = do [h, w] <- getInts grid <- getCharGrid ((1, 1), (h, w)) let s = fromGridGS (== '#') grid s' = fromGridGS (== '.') grid idx = accumArray @UArray (flip const) (-1) ((1, 1), (h, w)) $ zip (Set.toList s) [1 :: Int ..] uf <- newUF @IOUArray (1, Set.size s) (-1) for_ (Set.toList s) $ \v -> do for_ [(0, 1), (1, 0), (0, -1), (-1, 0)] $ \d -> do let u = v `add2` d when (Set.member u s) $ do unite uf (idx ! v) (idx ! u) size <- getNumComponents uf xs <- for (Set.toList s') $ \v -> do let us = filter (`Set.member` s) $ map (\d -> v `add2` d) [(0, 1), (1, 0), (0, -1), (-1, 0)] k = length us + 1 uf2 <- newUF @IOUArray (1, k) (-1) for_ (combinations 2 (zip [1 ..] us)) $ \[(i, u1), (j, u2)] -> do same <- isSame uf (idx ! u1) (idx ! u2) when same $ do unite uf2 i j before <- getNumComponents uf2 for_ [1 .. k - 1] $ \u -> do unite uf2 u k after <- getNumComponents uf2 return $ size - (before - 1 - after) let IntMod ans = sum (map IntMod xs) * invIntMod (IntMod (Set.size s')) print ans ``` が、小さな Union-Find をたくさんつくって判定するのは面白いのですが、わざわざこんなことをしなくてももとの Union-Find で既にグルーピングされてるのでそれを使えば良いのでした。 代表元の頂点番号をグループIDと見なして、そのユニーク数を数えることで `.` の周囲 $4$ マスの頂点が連結成分何個を成しているか、分かります。 ```haskell main :: IO () main = do [h, w] <- getInts grid <- getCharGrid ((1, 1), (h, w)) let b = bounds grid (vs, vs') = bimap (map fst) (map fst) $ partition ((== '#') . snd) (assocs grid) n = length vs n' = length vs' idx = accumArray @UArray (flip const) (-1) ((1, 1), (h, w)) $ zip vs [1 :: Int ..] uf <- newUF @IOUArray (1, n) (-1) for_ vs $ \v -> do for_ [(0, 1), (1, 0), (0, -1), (-1, 0)] $ \d -> do let u = v `add2` d when (inRange b u && grid ! u == '#') $ do unite uf (idx ! v) (idx ! u) size <- getNumComponents uf xs <- for vs' $ \v -> do let us = filter (\u -> inRange b u && grid ! u == '#') $ map (\d -> v `add2` d) [(0, 1), (1, 0), (0, -1), (-1, 0)] x <- length . nub <gt; traverse (\u -> root uf (idx ! u)) us return $ size - (x - 1) let IntMod ans = sum (map IntMod xs) * invIntMod (IntMod n') print ans ``` ---- ## 感想など ![[スクリーンショット 2023-12-24 8.24.23.png]] 今回で 1000 に載せて年明けから改めて水色を目指そう、という展開を描いていたのですがそうは問屋が卸さず。 2023年はレート 952 でフィニッシュでした。 より上位レートのみなさんに比較すると、今回は経験の差がでたなあと思いました。 B や C を後回しにしてさっさと D や E を解いている方が多く、私もたとえ序盤の問題であろうと一時的に損切りする。これができればよかったです。 ただ B、C 両方損切りしてその後にリカバリできている人は殆どいないですね。 B か C どちらかでいいのでシュッと解くことが出来れば、切るのは一問で良いので、それならよくあることというので平静を保つことはできたかも知れません。B, C 両方とばして D, E を涼しい顔で解く、という鋼のメンタルを手に入れるには長い時間がかかりそうです。 レートはここ１ヶ月、横ばってますね。 年末年始しっかり練習して、改めて1月にはここを脱出したいと思います 🔥