# ABC434 振り返り - [Ｓｋｙ Inc, Programming Contest 2025 (AtCoder Beginner Contest 434) - AtCoder](https://atcoder.jp/contests/abc434) - ABCDE 5完 (1689) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc434) ![[スクリーンショット 2025-11-30 10.35.55.png]] ABC434 でした。 今回も首尾良く 5完できて、青パフォでした。 - A (灰) ··· 割り算して $+1$ - B (灰) ··· 種類ごとに個数、大きさの和を数えて平均を計算 - C (茶) ··· (下界、上界) を状態にもって更新する - D (緑) ··· 二次元いもす法と二次元累積和。$i$ の雲の領域で雲の重なり数が 1 になってるところを二次元累積和で数える - E (水) ··· ジャンプ先の座標をグラフの頂点に見立てる。グラフの頂点数が寄与数。連結成分が木なら $-1$ atcoder-standing-difficulty-analyzer による E の推定難易度は 1388 とかです。AtCoder Problems 的な難易度は更にここから少し下がる。 今回の E を 70分で 5完しても、かつてのスコア計算でいくと 1689 も行く感じがしないです。せいぜい 1400 前後ぐらいだったと思います。 やはり基準値変更で、良いパフォーマンスが出やすくなってそうです。でなければ4連続青パフォはできすぎ。 他の人をみても ABC430 あたりから上向いてる人が多いので、そういことでしょう。 何にせよ、満足のいく結果です。今回も盆栽が役に立つ場面が多くありました。 ## [A - Balloon Trip](https://atcoder.jp/contests/abc434/tasks/abc434_a) 素直に割り算します。最初、よく考えず `ceildiv` を使っててサンプルが合わず ? となりました。 ```haskell main :: IO () main = do [w, b] <- getInts print $ (w * 1000) `div` b + 1 ``` ## [B - Bird Watching](https://atcoder.jp/contests/abc434/tasks/abc434_b) 最近 B が簡単ですね。 鳥の種類ごとに平均を取りたい、ので種類ごとに大きさと鳥の数をそれぞれバケットで数えて、平均を求めます。 ```haskell main :: IO () main = do [n, m] <- getInts vs <- replicateM n getTuple let bucket1 = IM.fromListWith (+) [(ai, bi) | (ai, bi) <- vs] bucket2 = IM.fromListWith (+) [(ai, 1 :: Int) | (ai, _) <- vs] for_ [1 .. m] $ \i -> do let s = bucket1 IM.! i c = bucket2 IM.! i print $ fromIntegral s / fromIntegral c ``` ## [C - Flapping Takahashi](https://atcoder.jp/contests/abc434/tasks/abc434_c) なんか問題文がややこしいですが。 飛行機は高度 $H$ を飛んでいる。 $t$ 秒間で $-t$ から $+t$ まで高度を変えることができる。 ある時刻 $t_i$ では $(l_i, u_i)$ の高度に飛行機はいる必要がある。 という問題です。 その時点で飛行機が取り得る高度の (下界, 上界) を状態に取り、それを更新していきます。 下界と上界は、$t$ 秒間で $-t$ から $+t$ まで拡がりますが、一方で制約として $(l_i, u_i)$ に収まらないといけない。 これを考慮して状態を更新していき、下界と上界が反転しないかどうかを調べる。 ```haskell main :: IO () main = do t_ <- getInt replicateM_ t_ $ do [n, h] <- getInts xs <- replicateM n getTuple3 let xs' = (0, minBound, maxBound) : xs res = scanl' f (h, h) $ zip xs' (tail xs') where f (low, high) ((t, _, _), (t', l, u)) = do let dt = t' - t (low', high') = (max l (low - dt), min u (high + dt)) (low', high') printYn $ all (uncurry (<=)) res ``` ## [D - Clouds](https://atcoder.jp/contests/abc434/tasks/abc434_d) ぱっと見で二次元累積和の問題。二次元累積和を使うことを前提に解法を組み立てていきます。 入力例 1 を、各マスに幾つの重なりがあるかで表現すると ``` 0 0 0 1 1 1 1 1 1 2 1 1 1 1 2 3 2 1 1 1 2 2 1 0 0 0 1 2 2 1 ``` このようになります。 このグリッドは入力に対して二次元いもす法 + 二次元累積和を使えば簡単に構築できます。 ここから $i$ の領域だけを取り除いたときに、グリッド全体で 0 が何個になるかを数えられれば良いです。 $i$ の領域を取り除いたとき新たに 0 になるのは、その領域の中に含まれる 1 の個数で分かります。 これを二次元累積和に対する部分和のクエリで計算します。 先のグリッドそのままで、1の個数を数えるのは難しいので、このグリッドを更、マスの値が 1 のところだけのグリッドに写像して、そこから二次元累積和テーブルへ写像します。 これで雲 $i$ の領域に 1 が何個含まれるか、$O(1)$ で計算できます。 $i$ を取り除く前の 0 の数を予め数えておき、$i$ の領域に含まれる $1$ の数を足す。これが各 $i$ に対する答えになります。 ```haskell main :: IO () main = do n <- getInt blocks <- replicateM n $ do [u, d, l, r] <- getInts let u0 = u - 1 d0 = d l0 = l - 1 r0 = r return (u0, d0, l0, r0) let (h, w) = (6, 6) xs = [[((u, l), 1), ((d, r), 1), ((u, r), -1), ((d, l), -1)] | (u, d, l, r) <- blocks] grid = accumArray @UArray (+) 0 ((0, 0), (h, w)) (concat xs) s = fromArrayCS grid let ones = array @UArray ((0, 0), (h - 1, w - 1)) [(v, if s ! (v + 1) == 1 then 1 else 0) | v <- range ((0, 0), (h - 1, w - 1))] onesCS = fromArrayCS ones zero = h * w - countBy (> 0) (elems s) for_ blocks $ \(u, d, l, r) -> do let ans = zero + rectRangeSum onesCS (u, l) (d, r) print ans ``` なお、二次元累積和は素で実装すると実装がごちゃごちゃしやすいので、以下のように、二次元配列を二次元累積和に写像する関数および、その累積和オブジェクトに対して部分和の計算をクエリする関数を盆栽しておくと実装が楽です。 ```haskell {-- 2D CumSum --} -- グリッドの配列から二次元累積和を構築する (速度を稼ぐため MArray を利用) -- ((1,1), (h, w)) -> ((1, 1), (h + 1, w + 1)) になる (+1 は scanl の 0 が追加される) fromArrayCS :: UArray (Int, Int) Int -> UArray (Int, Int) Int fromArrayCS as = runSTUArray $ do s <- newArray b (0 :: Int) for_ (range (bounds as)) $ \(i, j) -> do writeArray s (i + 1, j + 1) (as ! (i, j)) for_ [(i, j) | i <- [lh .. uh + 1], j <- [lw .. uw]] $ \(i, j) -> do x <- readArray s (i, j) modifyArray s (i, j + 1) (+ x) for_ [(i, j) | j <- [lw .. uw + 1], i <- [lh .. uh]] $ \(i, j) -> do x <- readArray s (i, j) modifyArray s (i + 1, j) (+ x) return s where ((lh, lw), (uh, uw)) = bounds as b = ((lh, lw), (uh + 1, uw + 1)) -- 矩形部分領域計算の抽象 rectRangeQuery :: (Num a1) => ((a2, b) -> a1) -> (a2, b) -> (a2, b) -> a1 rectRangeQuery f (a, b) (c, d) = f (c, d) - f (a, d) - f (c, b) + f (a, b) -- 左上 (a, b) 右下 (c, d) に対する2次元累積和をクエリする -- 右半開区間でクエリする (例) queryCS s (a, b) (c + 1, d + 1) rectRangeSum :: UArray (Int, Int) Int -> (Int, Int) -> (Int, Int) -> Int -- FIXME: 本当はこう定義したいが関数呼び出しにより速度が犠牲になる -- rectRangeSum s = rectRangeQuery (s !) rectRangeSum s (a, b) (c, d) = s ! (c, d) - s ! (a, d) - s ! (c, b) + s ! (a, b) ``` ## [E - Distribute Bunnies](https://atcoder.jp/contests/abc434/tasks/abc434_e) グラフで考えると良い問題です。それさえわかれば簡単です。 ウサギは最初 $X_i$ にいますが、そこから $-R_i$ か $+R_i$ に移動することができます。 この移動先の座標をそれぞれ $u = X_i - R$ 、$v = X_i + R$ としグラフの頂点とみなします。 そして $(u, v)$ の間に無向辺があると考える。 これでグラフを構築してみると、複数の連結成分をもったグラフになることがわかります。 そしてそのグラフの頂点数が答えに寄与しているということも直感的にもわかります。 グラフの頂点がウサギが到達できる可能性のある座標を示しているので当然です。 例えば、入力例 $1$ をグラフにすると連結成分が 1 つで頂点数が 4 のグラフができあがります。一方で答えは 3 です。 これはウサギが到達できる頂点が合計で 4 つあるが、うち 1 つではウサギが被ってしまって、答えは 3 になるということを言ってます。 入力例 2 は、連結成分が 1 つで頂点数が 4 で、答えが 4 です。 ウサギが到達できる頂点が合計 4 つ、ウサギの被りなしで配置できて答えが 4 になる。 入力例 3 は、連結成分が 4 つ、頂点数の総和が 12 で、答えが 9 です。 3 箇所で被りがでる、ということを言っています。 このとき、入力例 1 の連結成分にはサイクルがありません。そして頂点数 4 に対して答えが 3。 入力例 2 の連結成分にはサイクルがあります。そして頂点数 4 に対して答えが 4。 どうも、サイクルのありなし･･･つまり連結成分が木かどうかが何か関係していそう。 違う角度で、連結成分の意味も考察してみます。 入力例 3 が分かりやすいのですが、4 つの連結成分は何を表しているか。 これは影響範し合うウサギのグループを表しています。ウサギのジャンプの選択が互いに影響しあうグループを表している。 例えば - A ウサギ : 3 か 7 に行ける - B ウサギ : 7 か 9 に行ける - C ウサギ : 9 か 12 に行ける として `3 - 7 - 9 - 12` となりますが、この 4 地点はウサギ A/B/C が「どちらに行くか」の選択によって影響し合う 4 地点。 仮に他に 100 とか 1000 とか遠くにウサギがいてジャンプ力も小さい場合、その遠いウサギはこの $(3, 7, 9, 12)$ のグループには何の影響も与えません。 こうして、影響を与えるウサギ同士のグループに分けると、それが連結成分になる。 このとき、サイクルのあるグラフには余裕があります。 あるウサギが選択肢 α にいったら、あるグラフはそう出ない選択肢 β にジャンプすれば良い･･･これを繰り返していったときに、好きなようにバランスを取ることが出来る。一方、サイクルがないと、どこかでバランスが取れずに詰まってしまう。 イメージとしては、スライドパズルのゲームに似てます。空きますがあって、パネルをスライドさせて数字を並び替えたりするやつ。 空きマスが 2 つとか余剰自由度があれば、好き放題にパネルを配置できるが、自由度が少ないと自由には動かせない。 サイクルのあるグラフには自由度的に余剰があり、木にはそれがない。 この問題の場合、サイクルがあれば循環させられる、つまり頂点すべてにバランスよくウサギを配置できるが、木の場合はどこか 1 つの頂点でウサギの被りがどうしても出てしまう、ということです。 というわけで - ジャンプ後のウサギの座標を頂点としたグラフに見立てる - なお、座標が大きいので座標圧縮する - Union-Find でグラフを構築して連結成分に分ける - 各連結成分が木かどうかを調べる (連結成分に含まれる辺の数が分かれば良い) ··· 木の場合は寄与数 $-1$ と実装すれば答えになります。 ```haskell main :: IO () main = do n <- getInt xs <- replicateM n getTuple let uvs = [(x + r, x - r) | (x, r) <- xs] vs = concat [[u, v] | (u, v) <- uvs] (rank, ix) = zaatsuRank @UArray 1 vs uvs' = [(ix u, ix v) | (u, v) <- uvs] uf <- newListUF @IOUArray (1, numElements rank) (-1) uvs' res <- mapM (isTreeUF uf . head) =<< getComponentsUF uf let ans = numElements rank - countBy (== True) res print ans ```