# ABC395 振り返り - [AtCoder Beginner Contest 395 - AtCoder](https://atcoder.jp/contests/abc395) ![[スクリーンショット 2025-03-02 9.41.13.png]] ABC395 でした 入水して初めての回でレートの貯金もないですし、即緑に戻ることもあるだろうなと思いましたが、終わってみれば初青パフォ。大きく勝つことができました。 - A (灰, 14) ··· `<` で隣合う値を比較して全部 True なら Yes - B (灰, 72) ··· 各層の層レベルの偶奇を調べる。各マスの層レベルは上下左右の外周から最も近い距離で決まる - C (灰, 161) ··· $A_i$ の出現位置を転置インデックスにして隣との距離をとる - D (緑, 919) ··· 鳩と巣の間に入れ物 (グループ) がある、と考えて 3 つの配列で管理。操作 2 では入れ物の場所を交換すれば OK - E (緑, 978) ··· 頂点倍化で普通の向きのグラフの世界と逆向きのグラフの世界を作り、二つの世界をコスト $X$ の無向辺で結んでダイクストラ法 - F (水, 1437) ··· 答えで二分探索。高さ $h$ にしたとき条件に収めることができるか? という関数 $f (h)$ を構成する。上の歯の下界と上界を考えて矛盾がないかを $O(N)$ でチェック ## [A - Strictly Increasing?](https://atcoder.jp/contests/abc395/tasks/abc395_a) 「狭義」単調増加なので、隣の値との比較を `<` で調べます ```haskell main :: IO () main = do n <- getInt as <- getInts let res = zipWith (<) as (tail as) printYn $ and res ``` ## [B - Make Target](https://atcoder.jp/contests/abc395/tasks/abc395_b) 外周から中心に向かって層をなしている。層のレベルの偶奇ごとに、その層の模様が `#` か `.` かが決まる、という構造になっています。 各マスがどの層レベルに属しているかはマスの座標 $(r, c)$ のうち上下左右の外周に最も近い距離で決まります。 ので $r, c, n + 1 - r, n + 1 - c$ の最小値の偶奇を調べるとよいです。 ```haskell main :: IO () main = do n <- getInt let grid = listArray @UArray ((1, 1), (n, n)) [ if odd d then '#' else '.' | (r, c) <- range ((1, 1), (n, n)), let d = minimum [r, c, n + 1 - r, n + 1 - c] ] printCharGrid grid ``` ## [C - Shortest Duplicate Subarray](https://atcoder.jp/contests/abc395/tasks/abc395_c) ある $A_i$ があったとき、次に $A_i$ と同じ値が出てくる場所はどこか? を調べる問題と言い換えられます。 各数字の出現位置を、転置インデックス (数字をキーにして、その数字が出現する位置のリストを辞書にする) を作ります。 あとは転置インデックスで隣との距離を計算して、その最小値を取れば OK です。 ```haskell main :: IO () main = do n <- getInt as <- getInts let g = IM.map sort $ imGraph $ zip as [1 :: Int ..] res = concat [zipWith (\a b -> a + 1 - b) (tail vs) vs | vs <- IM.elems g] print $ minimumDef (-1) res ``` ## [D - Pigeon Swap](https://atcoder.jp/contests/abc395/tasks/abc395_d) 操作 $2$ をどうするか、がポイントになる問題です。 二つの巣に入っている鳩を一斉に入れ換えますが、一つ一つ鳩の居場所をつきとめて入れ換えていたのでは最大で $O(N)$ かかってしまうでしょう。 そこで、鳩と巣の間に中間の入れ物を考えます。鳩はその中間の入れ物に入っていて、その入れ物が巣の中にあるとする。 こうすれば操作 2 では入れ物がどの巣に属すかだけを交換すればよいので、$O(1)$ で済みます。 プログラミングにおける参照渡しのような考え方です。 操作 2 では必ず入れ物は 1 対 1 で交換されるので、特定の巣に複数の入れ物が属すことはありません。 というわけで配列としては - 鳩がどの入れ物 (グループ) に属しているか - 巣がどの入れ物をもっているか - 入れ物がどの巣にあるか の三つの配列をもって、シミュレーションしていけばよいです。 ```haskell main :: IO () main = do [n, q] <- getInts qs <- replicateM q getInts pigeons <- newListArray @IOUArray (1, n) [1 .. n] hiveToGroup <- newListArray @IOUArray (1, n) [1 .. n] groupToHive <- newListArray @IOUArray (1, n) [1 .. n] for_ qs $ \case [1, a, b] -> do gi <- readArray hiveToGroup b writeArray pigeons a gi [2, a, b] -> do gi <- readArray hiveToGroup a gj <- readArray hiveToGroup b swapArray hiveToGroup a b swapArray groupToHive gi gj [3, a] -> do gi <- readArray pigeons a i <- readArray groupToHive gi print i _ -> error "invalid" ``` ## [E - Flip Edge](https://atcoder.jp/contests/abc395/tasks/abc395_e) [ABC277 E - Crystal Switches](https://atcoder.jp/contests/abc277/tasks/abc277_e) を彷彿させる問題です。 普通に構築したグラフを $G_1$ 、辺が逆向きのグラフを $G_2$ とする。スイッチを押すと $G_1$ の世界にいたのが $G_2$ の世界に切り替わる。 世界の切り替えコストは $X$ です。 こういう、二つの世界のグラフを行き来しつつグラフアルゴリズムを使いたいときは「頂点倍化」のテクニックを使う。 グラフ $G_1$ には頂点 $[1 \ldots N]$ が属していて、グラフ $G_2$ には頂点 $[Ｎ + 1 \dots 2N]$ が属す。 このとき、たとえば頂点 $1$ と $N + 1$ は鏡の関係になっている。表の世界の頂点 $1$ が $1$ で、裏の世界の頂点 $1$ が $N + 1$ (ファイナルファンタジーとかの裏の世界、みたいな厨二設定が少しわくわくします) グラフ $G_1$ と $G_2$ を橋渡しする辺は、この鏡の関係で対になっている $1$ と $N + 1$ を結ぶ辺です。そのコストは $X$ の無向辺にする。 これで頂点 $1$ からダイクストラ法をして、頂点 $N$ または $2N$ のいずれかに到達する最小コストを求めるとよいです。 ```haskell main :: IO () main = do [n, m, x] <- getInts uvs <- replicateM m getTuple let es = concat [[((u, v), 1), ((n + v, n + u), 1)] | (u, v) <- uvs] es' = concat [[((v, n + v), x), ((n + v, v), x)] | v <- [1 .. n]] g = wGraph (1, 2 * n) $ es ++ es' dist = dijkstra (g !) (+) Minimize maxBound (bounds g) (2 * m) [(1, 0)] print $ min (dist ! n) (dist ! (2 * n)) ``` ## [F - Smooth Occlusion](https://atcoder.jp/contests/abc395/tasks/abc395_f) 問題の雰囲気から「答えで二分探索」の匂いがします。結果、そのとおりでした。 まず、この問題では上の歯と下の歯を合わせた歯の高さ $h$ が決まれば、支払う金額は簡単に求められます。 初期状態の歯の高さの合計を $total$ とすると、$N$ 本の歯を高さ $h$ になるまで削るには $total - n \times h$ の支払金額となります。 実際、入力例 $1$ は ``` 4 3 -- N, X 3 1 4 1 5 9 2 6 ``` で $total = 31$ ですが、最適解は $h = 4$ で支払い金額は $31 - 4 \times 4 = 15$ になります。 次に問題設定の「歯がうまく噛み合っている」という条件について考えてみます。 歯の高さ $h$ が揃っていて、かつ上の歯において隣の歯との高さの差が $X$ 以内であれば良い、というのが条件です。 下界を考えると、 $h = 0$ のときは必ず条件が成立することがわかります。これは初期状態から歯を全部削る事に相当するので、支払金額としては最大。 $h$ を大きくしていくと、支払金額は減っていきますが、削れる余地がその分減っていくので、どこかで高さの差を $X$ に収められない状態となりそうです。 つまり $f (h)$ を「歯の高さを $h$ にしたいとき、条件を満たすか?」という関数だと考えると、$f$ には単調性があることがわかります。 答えで二分探索、の出番です。あとは $f$ をどう構成するか? です。答えで二分探索なら $f$ は $O(N)$ 程度かかっても問題ないので、そのつもりで考えます。 歯の高さを $h$ に調整するということは、かりに上の歯を $x$ にすると、下の歯は $h - x$ ということになって、上の歯の高さと下の歯の高さは連動することがわかります。 上の歯についてコンテキストを合わせて考えていきます。 $h$ に揃えるという前提のもと、各上の歯を削ることを考えると - 下の歯を一切削らない場合、上の歯ですべて調整して $h$ にする必要があり、これが下界で $max(0, h - D_i)$ - 逆に、下の歯を削れるところまで削って調整する場合が上の歯の上界で $min(U_i, h)$ と考えることができます。これで $1 \ldots N$ までの歯の上界と下界がわかりました。 あとは高さ $h$ としたとき、この上界と下界で条件··· 隣り合うの歯との差が $X$ に収まるか、を矛盾なく満たすことができるかを調べることができれば良いでしょう。 歯を左からみていって、前の歯の上界と下界を $X$ まで拡げた範囲と、現在の歯の範囲の交わりが空でないかをチェックします。 これを繰り返して、すべての歯について交わりが空でなければ、関数 $f(h)$ はその $h$ で条件を満たす、つまり $True$ を返すことができます。そうでなければ $False$ これを二分探索にかけます。二分探索の下界と上界は、下界が $0$ であり、上界が初期状態の上下の歯の合計がもっとも低い値でよいです。 ```haskell f x xs h = do let ranges = [(lb, ub) | (u, d) <- xs, let lb = max 0 (h - d), let ub = min u h] res = foldM step (head ranges) (tail ranges) where step (curLB, curUB) (lb, ub) = let lb' = max lb (curLB - x) ub' = min ub (curUB + x) in if lb' <= ub' then Just (lb', ub') else Nothing isJust res main :: IO () main = do [n, x] <- getInts xs <- replicateM n getTuple let hs = map (\(u, d) -> u + d) xs total = sum hs hMax = minimum hs (h, _) = bisect2 (-1, hMax + 1) $ f x xs print $ total - n * h ``` ## 感想など D の実装で詰まった人が多かったようですが「鳩を抽象的な入れ物に入れて、巣にはその入れ物を入れる」という方針をクリアに立てて頭でイメージできたので、それほど沼らずに済みました。実装しながら考えると頭が沸騰しそう、こういうときこそモデルを頭に描くことが重要です。 E は「スイッチを押すとグラフが切り替わる」というモデルで、これは類題が幾つかあるのですぐ解法が思いつきました。 ダイクストラ法は良い盆栽をもっているので、グラフさえ構成できればあとは一瞬。 E が 10 分弱で解けて、開始から 30分経過で 5完。のこり 70分を F に充てられたのは精神的にもかなり余裕が生まれて、おかげで F をじっくり考察することができました。 F はいかにも答えで二分探索の顔をしていたので、初めからその前提で固めて思考していきましたが、それが功を奏しました。 答えで二分探索の問題は上界と下界を考えると思考しやすいことが多いですが、この問題はまさにそういう問題でした。 ![[スクリーンショット 2025-03-02 14.56.06.png]] - 前々回は初めて 6完 - 前回で入水 - 今回は初めて青パフォ というのでここ 3回はとても調子が良いです。 この調子がずっと続けばいいなとおもいつつ、停滞期がしばらく続いてそれを脱出して次のステージに入る、というのをこれまで幾度と繰り返してここまで来たので、今回も例に漏れず···いまは好調な時期なだけ、なんだろうと思います。このタイミングで貯金を伸ばしておきたいです。