# ABC367 振り返り - [AtCoder Beginner Contest 367 - AtCoder](https://atcoder.jp/contests/abc367) - ABCDE 5完 (1360) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc367) ![[スクリーンショット 2024-08-18 11.56.40.png]] ABC367 でした。 久しぶりに 5完できて、パフォーマンスも 1360 と満足のいく結果でした。 - A (灰) ··· if で $B$ と $C$ の大小関係をもとに分岐 - B (灰) ··· 数字を文字列で扱い末尾から `0` と `.` を削除する - C (灰) ··· 再帰的に数列を生成する - D (緑) ··· 円環 + 累積和を $\bmod M$ に写像、$N - 1$ 個までの間に同じ値が何個あるか数える - E (水) ··· ダブリング - F (水, upsolve) ··· Zorbist Hash を $(+)$ で結合し、累積和で区間ハッシュ でした。 D が結構難しいと感じて、簡単には解けなそうなので E をみたところ瞬時にダブリングだとわかったので先に E を解き、残り時間を D に充てました。 D は解法がわかってからも実装で手間取り、終了間際になんとか仕上げて送信。通りました。 あと 11秒というところで、AC ときおり、終了ぎりぎりで AC したという話を見かけることがありますが、初めての経験でした。これはアドレナリンが出ますね 笑  ## [A - Shout Everyday](https://atcoder.jp/contests/abc367/tasks/abc367_a) A 問題にしてはやや面倒。 $B$ と $C$ の大小関係に注意して適切に分岐します。 ```haskell main :: IO () main = do [a, b, c] <- getInts let result = if b > c then a >= c && a < b else a >= c || a < b printYn result ``` ## [B - Cut .0](https://atcoder.jp/contests/abc367/tasks/abc367_b) 文字列のまま扱うのが簡単です。 問題文に従い、まず末尾から続く `0` を取り除く その後 `.` があるようならそれも取り除く ```haskell main :: IO () main = do x <- getLine let x' = dropWhileEnd (== '.') . dropWhileEnd (== '0') $ x putStrLn x' ``` ## [C - Enumerate Sequences](https://atcoder.jp/contests/abc367/tasks/abc367_c) $N$ や $K$ の制約がとても小さく「全部列挙しろ」と言わんばかりの問題。 例えば $(R_1, R_2, R_3 ) = (2, 1, 3)$ のときは以下のようなグラフの遷移を考えると良いです。 このグラフ遷移を DFS、つまり再帰的に遷移させた結果を全列挙すると良いでしょう。 ![[IMG_1448.jpeg|400]] こういう再帰的かつ網羅的な状態遷移は Haskell は得意です。リストモナド (リスト内包表記) で一撃です。 遷移を全列挙した上、総和をとって $K$ の倍数になるもののみ、残す。 ```haskell -- >>> sequences [2, 1, 3] -- [[1,1,1],[1,1,2],[1,1,3],[2,1,1],[2,1,2],[2,1,3]] sequences :: [Int] -> [[Int]] sequences [] = [[]] sequences (x : xs) = [y : ys | y <- [1 .. x], ys <- sequences xs] main :: IO () main = do [n, k] <- getInts rs <- getInts let res = [xs | xs <- sequences rs, sum xs `mod` k == 0] for_ res printList ``` ## [D - Pedometer](https://atcoder.jp/contests/abc367/tasks/abc367_d) $N$ 個の休憩所は円環になっているので、まず $A_1 \ldots A_N$ を $2N 個$ に倍化して、円環データ構造にして考えます。 休憩所 $s$ から $t$ までの移動にかかるコストは、明らかにその区間の区間和です。 そこで円環にした $A_1 \ldots A_{2N}$ に対する累積和をとります。 コストが $M$ の倍数になる、ということは合同計算が視野に入るので先にこの累積和を $\bmod M$ に写像してみます。 ```haksell [2,1,4,3] -- 円環にする [2,1,4,3,2,1,4,3] -- 累積和にする [2,3,7,10,12,13,17,20] -- mod 3 をとる [2,0,1,1,0,1,2,2] ``` ある区間が $K$ の倍数になる条件は、$\bmod K$ に写像された数列において $S_r - S_l = 0 \pmod M$ になるような $(l, r)$ の $2$ ペアということになります。$\bmod M$ において同じ数同士であれば区間和として差をとったら $0$ (つまり $K$ の倍数) になるというのがその理由。 というわけで、$\bmod M$ に写像した累積和が同じ数になる2ペアを数えます。 ここまでは、それほど難しい考察ではないと思います。 円環にしている都合上、単に出現頻度を数えるだけではうまくいきません。 ある値からみて $N - 1$ 個離れたところまでに、何個同じ数があるか··· を数える必要があります。 手続き的に、$0 \ldots M - 1$ までの数の出現頻度を数えつつ、$N$ 個前の出頻度を $1$ 下げるというのを繰り返して数え上げます。 ここが難しく、手間取りましたがなんとか AC 出来ました。 ```haskell countRightOccurrences b n as = runST $ do acc <- newArray b (0 :: Int) :: ST s (STUArray s Int Int) res <- foldM (f acc) [] (assocs as) return $ reverse res where f acc counts (i, x) = do cur <- readArray acc x when (inRange (bounds as) (i - n)) $ modifyArray acc (as ! (i - n)) pred modifyArray acc x succ return $ cur : counts main :: IO () main = do [n, m] <- getInts as <- getInts let s = map (`mod` m) $ scanl1 (+) (as ++ as) sa = listArray @UArray (0, 2 * n - 1) s res = countRightOccurrences (0, m - 1) (n - 1) sa print $ sum $ drop n res ``` ## [E - Permute K times](https://atcoder.jp/contests/abc367/tasks/abc367_e) ある状態 $v$ から次の遷移 $u$ が静的に与えられている、つまり $f(v) = u$ が記述できて、その遷移を $K$ 回繰り返す。 $K \leq 10^{18}$ と非常に大きい。 この特徴はダブリングですね。ダブリングしろ、と言ってるような問題です。 ダブリングの盆栽で一撃···といいたいところですが本番ではフレームワークの使い方を微妙にわすれていて、素でダブリングを書きました。 以下はその後フレームワークに当てはめて解いた回答です。 ```haskell main :: IO () main = do [n, k] <- getInts xs <- getIntArray (1, n) as <- getIntArray (1, n) let dp = doubling @UArray (1, n) k (xs !) printList $ [as ! doublingFold dp k i | i <- [1 .. n]] {-- ダブリング --} doubling :: (IArray a v, Ix v) => (v, v) -> Int -> (v -> v) -> Array Int (a v v) doubling b k fn = listArray @Array (0, log2LE k) $ take (log2LE k + 1) $ iterate' (\dp -> genArray b (\ !v -> dp ! (dp ! v))) (genArray b fn) doublingFold :: (IArray a v, Ix v) => Array Int (a v v) -> Int -> v -> v doublingFold dp k s = foldl' (\v i -> dp ! i ! v) s (doublingSteps k) -- >>> doublingSteps 5 -- [0,2] doublingSteps :: Int -> [Int] doublingSteps k = [i | (i, flag) <- indexed 0 (toBinary k), flag] ``` ## [F - Rearrange Query](https://atcoder.jp/contests/abc367/tasks/abc367_f) (upsolve) 数列の一部の区間を部分集合とみなし、指定された二つの数列の部分集合が一致するかを $O(1)$ で突合しろ、という問題です。 集合の $O(1)$ での突合といえば Zobrist Hash が使えます。 [ABC250 E - Prefix Equality](https://atcoder.jp/contests/abc250/tasks/abc250_e) が類題です。 が、ABC250 E とは異なりこの問題は xor で集合の結合を表現する典型的な Zobrist Hash では、うまく解けません。 一つは対象が多重集合になること。もう一つは部分集合が $(L, R)$ 区間で与えられるので、区間ハッシュを求める必要がある点です。 どうやら「Zorbist Hash multiset」で検索すると以下の投稿に辿り着けるようです。  というわけでハッシュ値の結合に xor ではなく和 ··· $(+)$ を使うことで多重集合に対応できるほか、$(+)$ で結合するなら逆元の $(-)$ が使えて累積演算による区間ハッシュの取得が可能になります。 これは知らなかったです。 Zorbist Hash は、登場する各要素に十分に大きな乱数値をハッシュ値として当てれば衝突確率が限りなく小さくなることを根拠にしているわけですが、一定の条件下では xor ではなく $(+)$ で結合してもハッシュが衝突しない、ということでしょうか。数学的なところは良く分かってません。 Zobrist Hash 自体は知っていたのですが、今回はそれだと難しいなあと考えて、発展の可能性を棄却してしまいました。 すぐには可能性を捨てず、そこからググるという機転が必要でした。 ```haskell import System.Random main :: IO () main = do [n, q] <- getInts as <- getInts bs <- getInts qs <- replicateM q $ do [l1, r1, l2, r2] <- getInts return ((l1, r1), (l2, r2)) gen <- newStdGen let table = HM.fromList $ zip (as ++ bs) (take (2 * n) $ randoms gen :: [Int]) s1 = listArray @UArray (1, n + 1) $ scanl' (+) 0 [table HM.! a | a <- as] s2 = listArray @UArray (1, n + 1) $ scanl' (+) 0 [table HM.! b | b <- bs] for_ qs $ \((l1, r1), (l2, r2)) -> do let a = s1 ! (r1 + 1) - s1 ! l1 b = s2 ! (r2 + 1) - s2 ! l2 printYn $ a == b ``` ## 感想など 5完で水色パフォーマンスで満足のいく結果です。 最近は常にパフォーマンス 1000 以上を必ずとることができていて、実力的にも安定してきている実感があります。 レートは +28 されて 1140 になりました。水色が見えてきましたが、大きくレートを落とさないことを前提に、あと 3 〜 4 回ぐらいは水色パフォーマンスを取る必要がありそう。ここからが正念場です。 ![[スクリーンショット 2024-08-18 12.59.37.png]] 自分は何をするにもコツコツ蓄積でやるタイプだと思いますが、それを絵に描いたようなグラフになっています。 緑になってもう少しで一年が経つところです。