# ABC397 振り返り - [オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397） - AtCoder](https://atcoder.jp/contests/abc397) - ABCDE 5完 (1619) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc397) ![[スクリーンショット 2025-03-16 23.05.23.png]] ABC397 でした。青パフォで大きく勝つことができました。 - A (灰) ··· 問題文通り分岐する - B (灰) ··· `ioio...` の文字列を全パターン生成しても計算量的に問題ないので、$S$ が部分列になるまで生成する - C (灰) ··· IntMultiSet を二本持って畳み込む - D (水) ··· 数学問題。因数分解して $x - y = a$ と置いて $y$ の二次方程式にし、解の公式。その上で $a$ を固定して全探索。探索範囲は $1 \leq a \leq 10^6$ で OK - E (水) ··· 木DP。葉から根に向かって貪欲に長さ $K$ のパスを作っていき、丁度 $N$ 本になったら Yes。親では未解決パスをペアリングして、解決済みを作っていく。 ※難易度の色は推定 D 問題はオーバーフローで 1WA を出したものの式変形に躓くこともなく、それほど時間をかけずに解くことができました。 今回はこの D に落とし穴がいろいろあったためか、かなり多くの人が WA を出して躓いていました。 この時点でスコアにも余裕ができました。 続く E 問題は問題文の理解と実装に時間を要しましたが、D を解いて余裕があったため落ち着いて処理できました。 B, C, D あたり、Haskell の特長に助けられた部分が多かったです。 しかしこのところ調子が良すぎて、そのうち盛大にやらかしそうで怖いです。 ## [A - Thermometer](https://atcoder.jp/contests/abc397/tasks/abc397_a) 入力を Double で受け取り、問題文のとおり分岐します ```haskell solve x | x >= 38.0 = 1 | x >= 37.5 = 2 | otherwise = 3 main :: IO () main = do x <- readLn @Double print $ solve x ``` ## [B - Ticket Gate Log](https://atcoder.jp/contests/abc397/tasks/abc397_b) `isSubsequence` 関数を以前に実装していたものがあったので、これを使ってゴリ押し $S$ は $100$ 文字以下なので、最大でも条件を満たす変更後の文字 $S'$ は $200$ 文字程度のはずです。`iiiii...` のときなどに最大になる。 $S'$ を $2, 4, 6, 8 \ldots$ と全パターン生成しても間に合います。 Haskell には `cycle` という便利な関数があり、これを使えば `ioioioioio...` と繰り返す文字列を簡単に生成できます。 `ioio...` という文字列を $2$ 文字ずつ伸ばしていって、$S$ がその部分列になっているかを判定し、部分列になったところで停める。 生成された $S'$ の長さと元の文字列 $S$ の長さの差を取れば、操作回数が分かります。 ```haskell -- xs が ys の部分列になっているか isSubsequence :: Eq a => [a] -> [a] -> Bool isSubsequence [] _ = True isSubsequence _ [] = False isSubsequence (x : xs) (y : ys) | x == y = isSubsequence xs ys | otherwise = isSubsequence (x : xs) ys main :: IO () main = do s <- getLine let k = until (\n -> isSubsequence s (take n $ cycle "io")) (+ 2) 0 print $ k - length s ``` ### 追記 Data.List に `isSubsequenceOf` があったのをすっかり忘れていました ```haskell main :: IO () main = do s <- getLine let k = until (\m -> s `isSubsequenceOf` take m (cycle "io")) (+ 2) 0 print $ k - length s ``` ## [C - Variety Split Easy](https://atcoder.jp/contests/abc397/tasks/abc397_c) 例えば入力例 1 の $(3, 1, 4, 1, 5)$ であれば、左側を $(3)$ 右側を $(1, 4, 1, 5)$ からスタートし、右側から先頭の値を削除して左側に入れる。 これを繰り返せば良いです。 左側と右側の集合のデータ構造には multiset 相当の IntMultiSet を使います。IntMap ベースの多重集合の実装です。 IntMultiSet であれば挿入と削除は十分に速いです。また、集合内に何種類の値があるかを `distinctSizeMS` という関数で $O(1)$ で計算できるようにしてあるので、それを使って左と右の種類数を求める。 ところで IntMultiSet は永続データ構造なので、以下の実装のように `scanl'` で先に集合操作の履歴すべてを作ってしまい、その後に各局面での左右の集合に含まれる値の種類数に変換する、という芸当が可能です。永続データ構造を使うとこのように計算を分割できて、認知負荷を下げることができます。 ```haskell main :: IO () main = do _ <- getInt as <- getInts let left0 = singletonMS (head as) right0 = fromListMS (tail as) ss = scanl' f (left0, right0) (init . tail $ as) where f (left, right) a = (insertMS a left, deleteMS a right) res = [distinctSizeMS left + distinctSizeMS right | (left, right) <- ss] print $ maximum res ``` ## [D - Cubes](https://atcoder.jp/contests/abc397/tasks/abc397_d) 中学 (高校?) 数学程度の基礎的な式変形と、利用しているプログラミング言語の数値周りの仕様の正しい理解が要求される問題でした。 $x^3 - y^3 = N$ はいかにも因数分解で整理できそうな式なので、それを使います。また、その後に二次方程式の解の公式を使います。 まず問題文をよく読むと $x > 0、$ $y > 0$ 、$N > 0$ です。 また $x^3 - y^3 = N$ で、$x, y, N$ すべて正なので $x > y$ であることも分かります。 さて式変形です。 $x^3 - y^3 = N$ $(x - y)(x ^2 + xy + y^2) = N$ ここで $x - y = a$ とおくと $a(x^2 + xy + y^2) = N$ $x^2 + xy + y^2 = \frac{N}{a}$ $x - y = a$ より $x = a + y$ であり、これを $x$ に代入すると $(a + y)^2 + (a + y)y + y^2 = \frac{N}{a}$ $y^2 + 2ay + a^2 + y^2 + ay + y^2 - \frac{N}{a} = 0$ $3y^2 + 3ay + (a^2 - \frac{N}{a}) = 0$ となります。二次方程式になりました。 解の公式を使いたいので $A = 3, B = 3a, C = a^2 - \frac{N}{a}$ と置くと $Ay^2 + By + C = 0 $ $y = \frac{-B \pm \sqrt{B^2 - 4AC}}{2A}$です。$A, B, C$ の値を先の具体的な値に置き換えます $y = \frac{-(3a) \pm \sqrt{(3a)^2 - 12(a^2 - \frac{N}{a})}}{6}$ となります。ここで判別式 (平方根の中の値) を $D$ とすると $y = \frac{-3a \pm \sqrt{D}}{6}$ となります。また $D = (3a)^2 - 12(a^2 - \frac{N}{a})$ $D = 9a^2 - 12a^2 + 12\frac{N}{a}$$D = 12\frac{N}{a} - 3a^2$ となります。 $y$ や $D$ は $a$ に依存していてそれ以外は定数です。$a$ を固定して全探索できれば問題が解決できそうな雰囲気がしますが、いったんそれは脇におきます。 式をよく眺めます。 - $y$ は正の整数なので、$D$ は平方数である必要があります。$D$ が平方数でなかった場合 $\sqrt{D}$ が整数にならないため $y$ も整数でなくなってしまいます。 - 同様に分子は $6$ で割り切れる必要があります - $N$ は $a$ で割り切れる必要があります。 - $\pm \sqrt{D}$ のうち $\pm$ が $-$ のケースは、分子全体が負の値になって $y > 0$ に反することから $+$ のケースだけ考慮すれば良いです このあたり難しいように見えますが、サンプルのテストがこの辺をチェックしてないと落ちるようになっています。 さて、全探索の方針を考えていきます。 $x - y = a$ で $a$ がまだ二変数に依存しているのをどうするか。 ここで $x^3 - y^3 = N$ を改めて見てみます。似たような形の $a^3 = (x - y)^3$ との比較を考えると常に $x^3 - y^3 \geq (x - y)^3$ が成立します。 よって $N \geq a^3$ ということになり $1 \leq a \leq \sqrt[3]{N}$ であることがわかります。 $N$ の上界は $10^{18}$ なので、$a$ を $10^6$ まで全探索すればいいことを示唆しています。 この $a$ の探索範囲を絞り込むのを理屈だけから探るのは少し難しいと思いました。 自分は $N \leq 10^{18}$ という制約と $3$ 乗値が出てくることから、おそらく $10^6$ の全探索だろう、という類題からのメタ読みをして当てにいきました。 さて、これで全部揃います。$a = 1 \ldots 10^6$ まで $a$ を固定して全探索です。 先の解の公式で $y$ を求めます。$y$ が求まれば $x = y + a$ です。 - $N$ は $a$ で割り切れる - $D$ は平方数である - 分子は $6$ で割り切れる - $y$ は正の整数である をチェックして、違反している場合はそのケースは解なし、とします。 実装中にコメントしているとおり 64 bit 整数だと $D$ の計算でオーバーフローが生じますが、Haskell なら多倍長整数で難なくクリアできます。 また Haskell は多倍長整数があるだけでなく、数値演算周りは適当な理解では扱えない仕様になっていて訓練されているため、扱いにはそれなりに自信があります。 本番では $a$ の探索範囲の上界を求めるために真面目に $\sqrt[3]N$ を計算しましたが、結局 $10^6$ 決め打ちで問題なかったです。 ```haskell main :: IO () main = do n <- getInteger case mapMaybe (f n) [1 .. 10 ^ 6] of [] -> print (-1 :: Int) xs -> printTuple $ head xs f n a | n `mod` a /= 0 = Nothing | not (isSquareNumber d) = Nothing | k `mod` 6 /= 0 = Nothing | y <= 0 = Nothing | otherwise = Just (x, y) where x = y + a d = 12 * (n `div` a) - 3 * a * a -- Integer じゃないとここで 12 * 10^18 になりオーバーフローする k = -3 * a + isqrt d y = k `div` 6 ``` ## [E - Path Decomposition of a Tree](https://atcoder.jp/contests/abc397/tasks/abc397_e) 問題文の正確な理解が重要な問題です。 重要なのは「長さ $K$ のパス」のパスがどんな形をしているか、です。結論、頂点数 $K$ 個で一直線にできるのがパスであり、一直線にできない枝分かれした部分木はたとえ $K$ 頂点を含んでいてもパスではないです。最初ここが分かっていなくて、悩みました。 一直線のパスだと分かれば、戦略自体はそこまで難しくないです。 一直線のパスであれば、葉から貪欲に長さ $K$ のパスを作っていって、根に辿り着いたときにちょうど $N$ 本になっていて、すべての辺を使っていればよいわけです。 - 入力例 $1$ は木が単純な形をしているので、葉から長さ $K$ になったところで一区切りして根までみていけば分解が完了することがわかります。 - 入力例 $2$ は同じ戦略をとると、頂点 $3$ を親としたとき、頂点 $4$ もしくは頂点 $6$ のいずれかを破棄する必要があり、そこで矛盾があることがわかります。 この戦略は根はどこを選んでも成立します。 根がどこでもいいなら木DP が使えます。木DP で、葉から「未解決なパスの長さ (辺の長さ)」を親に向かって伝搬させていきます。 親は子たちから未解決なパスの長さを受け取ります。 このとき、親への辺を加えて長さが $K - 1$ になった未解決パスは、解決済みなので脇に寄せます。 残った未解決パスは、そのうち二つをペアにしてくっつけると、解決済みパスにできる可能性があります。 ペアリングがうまくいけば、子どもから受け取った未解決パスは全てなくなるか、$1$ つだけに限られるはずです。もし $2$ つ以上残る場合は枝分かれができてしまうことを意味し、パスへの分解に失敗することを意味します。入力例 $2$ で矛盾が発生したようなケースですね。 ペアリングは、矛盾がないケースであれば必ず最大数のペアができることがわかっているので、子から上がってきた未解決パスの候補のうち、最小と最大をそれぞれ選んで貪欲にペアリングしていく、でうまくいきます。それをしても $2$ 個以上未解決パスが残ってしまうケースは、そもそもが矛盾するケースです。 これを実装します。 ```haskell main :: IO () main = do [n, k] <- getInts uvs <- replicateM (n * k - 1) getTuple let g = graph2 (1, n * k) uvs tree = accumArrayTree @Array (g !) 1 (flip const) (Just (1, 0)) (bounds g) [] dp = accumTreeBottomUp f tree where f _ Nothing = Nothing f vs (Just (_, !acc)) = do case sequenceA vs of Just vs' -> do let (ds, accs) = unzip vs' ds' = case filter (/= -1) ds of [] -> [0] -- 子からの伝搬がない -> 現在の頂点からパスを開始 ds_ -> map succ ds_ (ps, remain) = partition (== k - 1) ds' (s', p) = deletePairs (fromListMS remain) 0 -- ペアリングして2本以上未解決パスが残る -> 枝の切り捨てが発生するため分解は失敗に終わる if sizeMS s' >= 2 then Nothing else Just ( if nullMS s' then (-1) else findMinMS s', acc + sum' accs + length ps + p ) Nothing -> Nothing deletePairs s acc | sizeMS s >= 2 && a + b == k - 1 = deletePairs s'' (acc + 1) | otherwise = (s, acc) where (a, s') = deleteFindMinMS s (b, s'') = deleteFindMaxMS s' case dp ! 1 of Just (d, acc) -> printYn $ d == -1 && acc == n Nothing -> putStrLn "No" ```