# ABC393 振り返り - [AtCoder Beginner Contest 393 - AtCoder](https://atcoder.jp/contests/abc393) - ABCDEF 6完 (1426) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc393) ![[スクリーンショット 2025-02-16 12.43.49.png]] ABC393 でした。 初めて 6 完できて良かったです。ただし E と F でペナルティが嵩んだため、パフォーマンスとしては 1400 程度。 ペナルティが少なければ青パフォが出ていたかもしれず、そこはもったいなかったです。 - A (灰, 10) ··· 2変数の組み合わせ 4パターンを全部記述する - B (灰, 44) ··· `combinations 3` で全探索 - C (灰, 188) ··· 多重辺と自己ループを取り除いた回数を計算する - D (茶, 533) ··· `1` のある位置の中央値に連続区間を合わせるように距離計算する - E (水, 1253) ··· 約数列挙でいけるが、同じ $A_i$ に対する約数列挙が何度も走らないようにする。Haskell → C++ 変換した - F (水, 1284) ··· クエリ先読み + 座標圧縮で、セグメント木を使って LIS を計算する過程でクエリを処理する ## [A - Poisonous Oyster](https://atcoder.jp/contests/abc393/tasks/abc393_a) 2変数なので組み合わせは 4 つ。全パターンの答えを頭で考えて記述してしまいます Haskell をやっているとこういう $2 \times 2 = 4$ のパターンマッチは良く書くので慣れています ```haskell solve s1 s2 = case (s1, s2) of ("fine", "fine") -> 4 ("sick", "sick") -> 1 ("sick", "fine") -> 2 ("fine", "sick") -> 3 main :: IO () main = do (s1, s2) <- auto @(String, String) print $ solve s1 s2 ``` ## [B - A..B..C](https://atcoder.jp/contests/abc393/tasks/abc393_b) 本番では位置 $(i, j, k)$ の3つ組なので、真ん中の $j$ すなわち `B` の登場位置に着目して、とやりました。 が、制約が緩いので `combinations 3` で全探索する方が実装も含めて楽でした ```haskell main :: IO () main = do s <- getLine let res = [ 1 :: Int | [(i, a), (j, b), (k, c)] <- combinations 3 $ indexed 1 s, [a, b, c] == "ABC", j - i == k - j ] print $ sum' res ``` ## [C - Make it Simple](https://atcoder.jp/contests/abc393/tasks/abc393_c) 辺のリストから自己ループと多重辺を取り除くだけ C にしては簡単すぎて ? となりました。 (それもあって最初、単純グラフにするのではなく連結にするのだと誤解し Union-Find を持ち出してしまい、余計な時間をロスしました) ```haskell main :: IO () main = do [_, m] <- getInts uvs <- replicateM m getTuple let uvs' = [if u < v then (u, v) else (v, u) | (u, v) <- uvs, u /= v] print $ m - (length . nubOrd') uvs' ``` ## [D - Swap to Gather](https://atcoder.jp/contests/abc393/tasks/abc393_d) `1` をどこに集めれば、散らばっている `1` を集めるコストが最小化するか? いろいろ解き方はありそうですが、中央値を使いました。 複数散らばった点があったとき、それらすべての点からの距離の総和を最小化する位置はどこか、これは中央値になる事実は良く知られています。競プロ典型 90問の [070 - Plant Planning（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_br) などで出題されています。 というわけで `1` のある位置をリスト化してその中央値をとる。 ここを`1` が集まったあとの連続区間の真ん中の位置にしたい。 $k$ 個の `1` を連続に並べるための区間を $[x, x + 1, \ldots, x + k - 1]$ と考えたとき、ここの中央が $x + mid$ であって欲しい $(mid = \frac{k}{2})$ `1` のある位置の中央値を $center$ とすると $center = x + mid$ となり、 $x = center - mid$ であり、先の区間の $x$ を置き換えると $[center -mid, center - mid + 1, \ldots, center -mid + k - 1]$ となる。 これが `1` を並べるときの理想的な位置。なので、あとはこの区間との差分をとっていけばよいです。 ```haskell main :: IO () main = do _ <- getInt s <- getLine let ones = [i | (i, c) <- indexed 0 s, c == '1'] k = length ones mid = k `div` 2 center = ones !! mid res = sum' [abs (pos - x) | (i, x) <- indexed 0 ones, let pos = center - mid + i] print res ``` ## [E - GCD of Subset](https://atcoder.jp/contests/abc393/tasks/abc393_e) 結論、Haskell だと TLE が取れなかったので C++ に変換して通しました。 $A_i$ を一つ選びつつ $K$ 個の要素を選んで GCD を最大化する、ということは $A_i$ を構成する約数と同じ約数のうちなるべく大きなものを他の $K - 1$ 個が持っていればよい、と考えられます。 計算量はいったん無視して、$A_1, A_2 \cdots A_N$ を全部約数列挙し、約数の値で出現頻度表 (バケット) を作る。 $A_i$ の約数とバケットを突合して約数が $K$ 個以上あったもののうち最大の値が、$A_i$ に対する答え。 という方針が立てられます。 問題は $N$ 個の $A_i$ を全部約数列挙するところ。普通にやると TLE します。 ここで $A_i \leq 10^6$ という制約に注目します。[高度合成数の一覧 | アルゴ式](https://algo-method.com/descriptions/92) によると $10^6$ でも約数は最大で $250$ 個程度しかない。 小さな値では約数は数個とかその程度であり、たとえ $N = 10^6$ でも値が綺麗に分散していれば $N$ 個全部に約数列挙しても間に合いそう。 しかし普通に計算すると TLE になるということは、大きな数がテストに多数含まれてる...分布が偏っている。つまり時間がかかるテストでは $A_i$ に同じ大きな値が被りまくっていると想像できます。 というわけで約数列挙の仕方を工夫し、同じ $A_i$ に対して約数列挙が最低限の回数で済むようにする。 [ABC292 C - Four Variables](https://atcoder.jp/contests/abc292/tasks/abc292_c) などで、$N$ までの約数の個数を倍数を使って効率的に求める問題がありました。 それと同様の手法で (約数の個数ではなく) 実際の約数を、倍数を使って求めていきます。`genDivisors`がその関数です。 実装をみるほうがはやいでしょう。 あとはこの生成した約数表を使って、各 $A_i$ の約数に対して、約数の数が $K$ 個以上になる最大の約数を見つけていけば OK です。 これで TLE は取れるか... と思ったのですが、Array を使っているせいか通らず。C++ に変換して 1148ms で通りました。 考察はあってそうなのに通らんなーと思い osa_k 法による高速素因数分解なども試したものの駄目。 定数倍のところかなあと思い C++ にしたら通りました。おかげで 4 ペナもらいました。 ```haskell genDivisors :: (Ix e', Num e', Enum e') => e' -> Array e' [e'] genDivisors n = accumArray @Array (flip (:)) [] (1, n) [(xx, x) | x <- [1 .. n], xx <- [x, x + x .. n]] main :: IO () main = do [n, k] <- getInts as <- getInts let maxA = maximum as divs = genDivisors maxA bucket = accumArray @UArray (+) 0 (1, maxA) [(d, 1) | a <- as, d <- divs ! a] res = [ maximum [d | d <- divs ! a, bucket ! d >= k] | a <- as ] for_ res print ``` なお、$A_i$ のユニークさえとれば通るようで、以下のように約数列挙を工夫せずとも通すことができました。C++ への変換は必要でした。 ```haskell main :: IO () main = do [n, k] <- getInts as <- getInts let as' = nubOrd' as dss = accumArray @Array (flip const) [] (1, 10 ^ 6) [(a, divisors a) | a <- as'] bucket = toBucket (1, 10 ^ 6) $ concat [dss ! a | a <- as] res = accumArray @UArray (flip const) 0 (1, 10 ^ 6) [(a, maximum [d | d <- dss ! a, bucket ! d >= k]) | a <- as'] for_ as $ \a -> print $ res ! a ``` Haskell でも Array ではなく Vector を使えば通るかもしれません。(私は Array 派です。) ## [F - Prefix LIS Query](https://atcoder.jp/contests/abc393/tasks/abc393_f) タイトル通り LIS の問題ですが、LIS をただ求めるのではなく、クエリに答える必要があります。 クエリの要求としては $[1 \dots R_i]$ 区間の $R_i$ が与えられて、その $R_i$ 区間の中で $X_i$ 以下の値で構成される部分列の LIS を求めよ、というもの。 一見難しそうですが、セグメント木なりを使った LIS の導出過程を理解していればこのクエリには容易に答えられることがわかります。 セグメント木で LIS を求めていく場合、数列 $A_1, A_2, \ldots, A_N$ を順番にみていって「$A_i$ を末尾の要素としたときの LIS 長」を木の葉に持たせます。 具体的には区間 max のセグメント木を用意し、$A_1, A_2, \ldots A_N$ をセグメント木のインデックスに対応させつつ、先の LIS 長を値とする。 これである $A_i$ に対して $[1, A_i)$ 区間の区間 max をとると、$A_i$ 未満の値の LIS が分かる。単一更新で $A_i$ の値をその LIS の値 $+1$ してやる。 これを繰り返すことで「$A_i$ を末尾の要素としたときの LIS 長」が計算できます。 ここをよく考えると、任意の $A_i$ の値に対する LIS はセグメント木が保持していることに気がつきます。 すなわち、ある区間 $[1, R_i)$ に対する $X_i$ 以下の LIS 長は、セグメント木を LIS 計算のために更新していく過程で計算されているわけです。$A_1, A_2 \ldots A_N$ まで全部 LIS を計算仕切ってから、ではなく、LIS を計算する途中でなら長さ $R_i$ に対するクエリに答えられます。 というわけでクエリを先読みして $R_i$ ごとに整理しておき、LIS を更新しながら数列 $A$ を長さ $R_i$ までみたところで $R_i$ に対応するクエリを処理します。 なお、$A_i$ や $X_i$ の値が $10^9$ になることもあるので、座標圧縮が必要です。セグメント木の問題ではよくあること。 ところで自分の中ではデータ構造を直接書き換える実装のデータ構造は「短命データ構造」という認識を持っています。 [永続データプログラミングと永続データ構造 - 一休.com Developers Blog](https://user-first.ikyu.co.jp/entry/2024/12/03/091133) 短命データ構造を繰り返し書き換えていく過程において、データ構造のある一状態には、書き換え直後のタイミングの一瞬にしかアクセスできません。対して、永続データ構造ならデータ構造の書き換え過程 (状態遷移過程) を全部残しておけるので、あとからそれらの過程の任意の状態にアクセスできます。 セグメント木は短命データ構造として実装していますが、今回の問題のように「計算途中ならクエリに答えられるのに」というケースは、むしろ「短命データ構造がゆえ、データ構造が欲しい状態にあるその一瞬にクエリ処理を挟み込めばよい」と考え直せば良く、結果、クエリ先読みという発想に至ります。対象のデータ構造が短命データ構造なのか永続データ構造なのかを明確に意識できると、こういう思考の整理に役立ちます。 ```haskell main :: IO () main = do [n, q] <- getInts as <- getInts qs <- replicateM q getTuple let (_, xs) = unzip qs (rank, ix) = zaatsuRank @UArray 1 (as ++ xs) dp <- newST @IOUArray max (0 :: Int) (1, numElements rank) let g = accumArray @Array (flip (:)) [] (1, n) [(r, (x, i)) | (i, (r, x)) <- indexed 1 qs] res <- for (indexed 1 as) $ \(r, a) -> do let idx = ix a lis <- rangeQueryST dp 1 idx updateST dp idx (`max` (lis + 1)) mapM ( \(x, i) -> do len <- rangeQueryST dp 1 (ix x + 1) return (i, len) ) (g ! r) for_ (sortOn' fst (concat res)) $ \(_, x) -> do print x ``` ## 感想など 初めて 6 完して、レートも Highest の 1188 になりました。 前回も 6完できたような問題セットだったのを逃して悔しい思いをしたので、素直に嬉しいです。 ![[スクリーンショット 2025-02-16 14.20.51.png]]いよいよ入水リーチですが、あまり意識するとずっこけそうなので次回以降も平常心で臨んで、結果水色になったらラッキーぐらいの気持ちでいたいです。