# ABC400 振り返り - [AtCoder Beginner Contest 400 - AtCoder](https://atcoder.jp/contests/abc400) - ABCDE 5完 (1645) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc400) ![[スクリーンショット 2025-04-06 8.58.51.png]] ABC400 でした。 C で躓きましたが、D は典型、E も部分問題に分解すれば典型問題だったためうまく解けて青パフォです。 どうも最近調子が良すぎて、自分でも少し驚いています。 - A (灰) ··· 400 `divMod` a - B (灰) ··· 多倍長整数を使ってオーバーフローを避ける - C (茶 or 緑) ··· $a$ を $1 \ldots \log{N}$ に固定して $b$ の数を数える。$b$ は奇数とすると、重複なく数えられる - D (緑) ··· 01-BFS の典型 - E (緑 or 水) ··· 上界見積もりからの全探索。400 number は平方数。予め全部列挙して順序付き集合でに各クエリに近い値を探す C 問題が予想外に難しい回でした。2ペナもらってこれはまずい、と思ったのですぐ D へ。 D が 01-BFS の典型問題で、これはみてすぐ解法がわかりました。D を解いたことで頭をリセットされたのか、その後 C を正しく考察できました。 E も C と似たような、上界を正しく見積もる問題。こちらは問題を丁寧に分解していくと複数の上界見積もり部分問題になりますが、いずれも茶 diff or 緑 diff でやったことがあるような典型的な見積もりゲームでした。 ## [A - ABC400 Party](https://atcoder.jp/contests/abc400/tasks/abc400_a) $400$ 人の髙橋君を $A$ 行全部同じ人数になるよう割り当てる、ので $400$ が $A$ で割り切れるなら、うまくいきます。 商と法を `divMod` で調べる。 ```haskell main :: IO () main = do a <- getInt print $ case 400 `divMod` a of (p, 0) -> p _ -> -1 ``` ## [B - Sum of Geometric Series](https://atcoder.jp/contests/abc400/tasks/abc400_b) ナイーブな実装で良いですが、Int で素直に計算するとオーバーフローが面倒。多倍長整数で実装すれば簡単です。 ```haskell main :: IO () main = do [n, m] <- getIntegers let x = sum' [n ^ i | i <- [0 .. m]] if x > 10 ^ 9 then putStrLn "inf" else print x ``` ## [C - 2^a b^2](https://atcoder.jp/contests/abc400/tasks/abc400_c) この手の問題は上界見積もりが肝です。上界を見積もることで $a$ または $b$ を固定して全探索できる可能性が見つかります。 $X = 2 ^ a \times b^2$ で $X$ は最大で $10^{18}$ です。 $b^2$ よりも $2^a$ の方が発散は速いので、$a$ の上界を見積もります。$N = 10^{18}$ かつ $b = 1$ のとき $a$ は最大で $N = 2 ^a$ になることから $a$ の上界は $\log{N}$ です。 というわけで $a$ を $[1 \cdots \log{N}]$ に固定して全探索します。 $b$ の個数は式変形により $b = \sqrt{\frac{N}{2^a}}$ です。 ```haskell main :: IO () main = do n <- getInt let res = [ b | a <- [1 .. log2LE n], let b = isqrt $ n `div` (2 ^ a) ] print $ sum' res ``` ただし、これで素直に計算すると条件を満たす整数を重複して数えてしまいます。上記の実装だとサンプルに対する答えが 5 になるところが → 7 24 → 43 42413 → 84816 となってしまい、数が大きくなっていくと 2倍弱多く数えてしまうことがわかります。この 2倍弱というところが実はポイントです。(それをみてピンときました) $X = 2^a \times b^2$ の式をみると、$a$ の方は $2^a$ になっていてそこに 2 の因子があることが分かります。 仮に $b$ に $2$ の因子が含まれる場合、$2^a$ の方で数えた分までダブって数えていることになります。 というわけで $b$ を奇数に絞り込んで数え上げると、辻褄が合います。$1 \dots b$ までに奇数が何個あるか? は $\lceil b/ 2\rceil$ で求められます。 ```haskell main :: IO () main = do n <- getInt let res = [ b `ceildiv` 2 | a <- [1 .. log2LE n], let b = isqrt $ n `div` (2 ^ a) ] print $ sum' res ``` ## [D - Takahashi the Wall Breaker](https://atcoder.jp/contests/abc400/tasks/abc400_d) 01-BFS の典型問題です。[ABC176 D - Wizard in Maze](https://atcoder.jp/contests/abc176/tasks/abc176_d) などが類題。 BFS っぽい問題だが遷移時に二通りの行動があり、その一方はコストがかからない、と来たら 01-BFS です。 普通に進むときは上下左右に 1 マスコスト $0$ で進むことができる。 前蹴りする場合は上下左右に 2マス、コスト $1$ で進むことができる。 と考えて状態遷移を定義すれば OK です。 ```haskell lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)] main :: IO () main = do [h, w] <- getInts grid <- getCharGrid ((1, 1), (h, w)) [a, b, c, d] <- getInts let start = (a, b) goal = (c, d) let dist = bfs01WithBuffer f (bounds grid) [(start, 0)] where f v = [(u, 0) | d <- lrud, let u = v + d, grid !? u == Just '.'] ++ [(u, 1) | d <- lrud ++ map (* 2) lrud, let u = v + d, grid !? u /= Nothing] print $ dist ! goal ``` ## [E - Ringo's Favorite Numbers 3](https://atcoder.jp/contests/abc400/tasks/abc400_e) C に引き続き上界見積もりゲームです。 正直、こちらの方が簡単でした。茶 〜 緑 diff でよくみる上界見積もりの部分問題を複数組み合わせたような問題でした。 まず、$10^{12}$ という中途半端な上界や、クエリに複数答えていく必要があることから上界を見積もり 400 number を予め列挙して探索、というような方針がうっすら見えます。 それを念頭に考察していくとよいでしょう。「平方」「累乗」あたりが上界を見積もるための重要なキーワードです。 さて、結論 400 number は平方数です。 素数 2 種類 $p, q$ で構成されていて各素数で割り切れる回数は偶数回ということは、$p$ と $q$ の指数は $2$ の倍数です。 $n = p^{2a} \times q^{2b} = (p^a \times q^b)^2$ となり、平方数になります。 $m = p^a \times q^b$ とすると $n = m^2$ で、$n \leq 10^{12}$ より $m \leq 10^6$ です。 また、$p$ と $q$ は異なる素数である必要があるので $p < q$ と考えてよいです。すると $p$ の上界は高々 $1000$ で良いこともわかります。 ここまでわかれば - $p$ は $1000$ までの素数を全探索 - $q$ は $10^6$ までの素数を全探索 という方針が見えて来ます。 加えて $p^a$ や $q^ b$ はそれぞれ $10^6$ が上界ですが、いずれも累乗であるため $p \times p \times p \cdots$ などはすぐに発散し、$10^6$ までの間にはそれほど多くの数がないこともわかります。 これらの条件を考慮すると 400 number を予め全て生成することができるので、あとは二分探索なり順序付き集合なりでクエリに一番近いものを探せば OK ```haskell main :: IO () main = do q_ <- getInt let s = IS.fromList [ m * m | p <- primes 1000, q <- takeWhile (<= 10 ^ 6 `div` p) [q | q <- primes (10 ^ 6), q > p], -- `div` p はしなくても通る pp <- takeWhile (<= 10 ^ 6) $ iterate (* p) p, qq <- takeWhile (<= 10 ^ 6) $ iterate (* q) q, let m = pp * qq, m <= 10 ^ 6 ] replicateM_ q_ $ do qi <- getInt print $ fromJust (IS.lookupLE qi s) ```