# ABC329 振り返り - [Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 329） - AtCoder](https://atcoder.jp/contests/abc329) - 成績 ABCDF 5完 (1287) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc329) ![[スクリーンショット 2023-11-19 11.34.39.png]] ABC329 でした。F を解いて 5完で、水色パフォーマンスでした。現時点のレートに対して満足のいく結果です。 - A (灰) ··· 文字列に空白を挟む。`join " "` 的なやつ - B (灰) ··· 2番目に大きな整数を見つける maximum 2回で OK - C (灰) ··· 連長圧縮して各文字ごとに最大の出現数を得る - D (灰) ··· その時点での最大値を一つ文脈に持ちながらバケットを更新する - E (水) ··· 解けず。上塗り系問題と自分は読んでいる。操作を逆から考えていく - F (水) ··· ボールを箱から箱に移す。だんだん大きな集合にまとまっていく。マージテクを使う典型らしいが Haskell では Set.union すればいい という問題セット。 D まで灰色ということで、ここ最近にしては中盤まで難易度が低い。そこから水色2問で、急に難易度が上がるという偏りのある問題セットでした。 開始前に配点を見て、少なくとも D までは早解きかなと思っていましたがその通りになりました。 E はちょっと取り組んでみて、これは結構大変そうだと感じたので飛ばして F へ。 最初 Union-Find を使ったものの、実装しきったところで間違いに気づきました。が、慌てず Set へ切り替えて AC。 集合と集合をマージするところで、他の言語では「マージテク」なるテクニックが必要らしく、TLE で苦戦している人が多かったようです。一方、Haskell の Set は `union` が結合する集合の大小関係を見ていい感じにやってくれるので、素直に実装するだけでよかったのが幸いしました。 D で凡ミスしていてちょっと沼ったり、F で Union-Find を使ってしまい実装をいちからやり直すというピンチな場面が何度かありましたが、うまくリカバリーできたのがよかったと思います。そういう状況でのメンタルコントロールができるようになってきた感があります。 ---- ## [A - Spread](https://atcoder.jp/contests/abc329/tasks/abc329_a) 文字と文字の間に空白を挟む。他の言語なら `join` なんかを使えば一発です。 Haskell にも `intersperse` という関数があるのですが、あまり使い慣れてないのでパッと出てこず。やや力技で実装しました。 ```haskell main :: IO () main = do s <- getLine putStrLn $ init $ concatMap (\c -> [c, ' ']) s ``` `intersperse` を使う場合は以下です。 intersperse (点在する) という単語に慣れてないというのも、すぐにこれが出てこない理由かも。 ```haskell putStrLn $ intersperse ' ' s ``` ---- ## [B - Next](https://atcoder.jp/contests/abc329/tasks/abc329_b) 数列の中から2番目に大きい整数を探す。やるだけです。 ```haskell main :: IO () main = do _ <- getInt as <- getInts let x = maximum as print $ maximum $ filter (/= x) as ``` ---- ## [C - Count xxx](https://atcoder.jp/contests/abc329/tasks/abc329_c) 文字列 $S$ の空でない部分文字列であって、$1$ 種類の文字のみからなるものの数を求める。 `aaabaa` とあったら `a,aa,aaa,b` の $4$ つが答え。 $S$ のサイズ的に $O(N^2)$ を回すと TLE するので、どうやって数えるか。 よく見ると `aaa b aa` と 2回 `a...` が出てきますが、長さの短い `aa` の方は答えの数に寄与しません。 それぞれの文字ごとに最も長い部分文字列の長さを求められれば良さそうです。 連長圧縮して、`accumArray` で文字種ごと max でたたみめば OK。 `accumArray` 大好きマンです。 ```haskell main :: IO () main = do _ <- getInt s <- getLine let xs = accumArray @UArray max (0 :: Int) ('a', 'z') $ rle s print $ sum (elems xs) ``` ---- ## [D - Election Quick Report](https://atcoder.jp/contests/abc329/tasks/abc329_d) 各得票数がその時点で最も大きな人を、開票のたびに出力する。 集合を動的に更新しながら、その都度、最大値を求めるというので最初はヒープか何かを使う問題かと思いましたが集合に入っている値も素早く更新する必要があるのでデータ構造一つでは難しそう。 関心があるのは最大値だけなので、その時点の最大値を文脈に保持しながら獲得票を計算していけば良いです。 開票のたび、最大値が更新されたかどうかを確認して、更新される場合は入れ替える。 ```haskell main :: IO () main = do [_, _] <- getInts as <- getInts foldM_ handler ((minimum as, 0 :: Int), IM.empty) as handler ((i, x), bucket) ai = do let bucket' = IM.insertWith (+) ai 1 bucket y = IM.findWithDefault 0 ai bucket' print $ if | x > y -> i | x == y -> min i ai | otherwise -> ai let ret = if | x > y -> (i, x) | x == y -> (min i ai, x) | otherwise -> (ai, y) return (ret, bucket') ``` ところで ```haskell let bucket' = IM.insertWith (+) ai 1 bucket y = IM.findWithDefault 0 ai bucket' ``` こういう、あるオブジェクトを更新してその更新結果から次の値を読み取るみたいな実装をよく書きますが、このとき後段では `bucket'` を使う必要があるのに更新前の `bucket` を使ってしまうというミスをしてしまいました。この間違い、よくやってしまいます。純粋関数が故の間違いポイントです。 これでも型チェックは通ってしまうので、間違いに気づきづらいのが難点。デバッグ含めて 10分弱ロスしました。 このミスを起こさないようなコーディング方法を考えていきたいです。 ---- ## [E - Stamp](https://atcoder.jp/contests/abc329/tasks/abc329_e) (upsolve) これは難しかったです。 例えば $T$ が `ABC` だったとして、`ABABC` という文字列を作るには先に `ABC##` を作ってそこから `C##` の箇所を上塗りするように `ABABC` と埋めます。 後から塗った箇所の方が優先されるというので、この手の問題を私は「上塗り問題」と呼んでます。 上塗り問題は、操作を、後ろから (逆から) 考えていくのが典型です。 この問題も例に漏れずで、逆から始めてその時点で $T$ で置き換えても良い位置を見つけていくのでうまくいきます。 入力例 $1$ の `ABCBABC` の場合 ``` 0123456 ------- ABCBABC <- [0, 4] が置換可能な開始位置 ###BABC <- [4] が置換可能な開始位置 ###B### <- 4 を埋めたことで [2] が新たに置換可能位置に ####### <- 全部 # にできたので ABCBABC は条件を満たす ``` と考えていきます。 ここまではわかったのですが、これをナイーブにやると操作のたびに文字列全体を走査する必要があって TLE してしまいます。 ポイントになるのは上記でいうところの、4 をうめたことで 2 が置換可能位置になったところ。$i$ を操作したとき、その結果他の位置が新たに置換位置になるのは `[i - m + 1 .. i + m - 1]` の範囲だけに限定されるので、文字列全体をつどスキャンする必要がありません。 ここに気がつけるかどうか、でした。 そして Haskell でこれを実装しようとすると、文字列を動的に書き換えながら、その時点で置換可能な文字位置をキューやスタックに積んで再帰する実装になると思います。動的な文字列更新となるとモナディックにする必要があります。 ($O(N)$ かけていいなら別ですが。) 今回は IO + MArray を使いました。 MArray を更新しながらスタックが空になるまで操作を続ける、みたいな実装を書くのはやや面倒で、本戦で焦って書くと多分はまるでしょう。 MArray ではなくイミュータブルな値が使えれば `takeWhile` や `iterate` などの高階関数が使えるので、楽なんですが。 これは解法に気がつけたとしても時間内に実装するのにも苦労したのではないかな、と思いました。 「解法がわかったからといって実装できるとは言っていません」 ![[スクリーンショット 2023-11-19 12.38.37.png|260]] ```haskell isOk buf n m t i = do s' <- mapM (readArray buf) $ filter (inRange (0, n - 1)) [i .. i + m - 1] return $ if | length s' /= m -> False | all (== '#') s' -> False | otherwise -> and $ zipWith f s' t where f '#' _ = True f a b = a == b loop _ _ _ _ [] = return () loop buf n m t (x : stack) = do for_ [x .. x + m - 1] $ \i -> do writeArray buf i '#' stack' <- foldM ( \acc i -> do ok <- isOk buf n m t i return $ if ok then i : acc else acc ) stack $ filter (\i -> inRange (0, n - 1) i && x /= i) [x - m + 1 .. x + m - 1] loop buf n m t stack' main :: IO () main = do [n, m] <- getInts s <- getLine t <- getLine buf <- newListArray @IOUArray (0, n - 1) s loop buf n m t (findString t s) s' <- getElems buf putStrLn $ if all (== '#') s' then "Yes" else "No" ``` ### 追記 ··· 左右から一回ずつやる 置換可能な位置をどう探すかですが、`[i - m + 1 .. i + m - 1]` を都度探索しなくても、左から `i = [0 .. n - 1]` を開始位置に置換可能なら置換、その後に右から `i = [n -1, n -2 .. 0]` にも同様にするだけでうまくいきます。 こちらの方が簡単ですし、速いですね。 ```haskell isOk buf n m t i = do s' <- mapM (readArray buf) $ filter (inRange (0, n - 1)) [i .. i + m - 1] return $ if | length s' /= m -> False | all (== '#') s' -> False | otherwise -> and $ zipWith f s' t where f '#' _ = True f a b = a == b main :: IO () main = do [n, m] <- getInts s <- getLine t <- getLine buf <- newListArray @IOUArray (0, n - 1) s for_ [0 .. n - 1] $ \i -> do ok <- isOk buf n m t i when ok $ for_ [i .. i + m - 1] $ \j -> do writeArray buf j '#' for_ [n - 1, n - 2 .. 0] $ \i -> do ok <- isOk buf n m t i when ok $ for_ [i .. i + m - 1] $ \j -> do writeArray buf j '#' s' <- getElems buf putStrLn $ if all (== '#') s' then "Yes" else "No" ``` ---- ## [F - Colored Ball](https://atcoder.jp/contests/abc329/tasks/abc329_f) 複数の箱があり、ボールが入っている。ある箱からある箱へボールを全部移し替える操作を行う。 ボールの集合とボールの集合が、操作のたびに結合して、一方の箱は空になりもう一方の箱には二つが合体した大きな集合が残る。 箱ごとに集合を一つずつ持って、操作のたびに `union` する、というのでうまくいきます。 Haskell の `Set.union` は結合する二つの集合のサイズの大小を見て計算量が少なく済む方向に結合をするように実装されています。 いわゆる「マージテク」を意識する必要はありません。 ![[スクリーンショット 2023-11-19 12.34.16.png]] おかげで、素直に実装するだけで AC できました。 ```haskell main :: IO () main = do [n, q] <- getInts cs <- getIntsArray (1, n) boxes <- newArray_ @IOArray (1, n) for_ [1 .. n] $ \i -> do writeArray boxes i (Set.singleton $ cs ! i) replicateM_ q $ do [a, b] <- getInts !x <- readArray boxes a !y <- readArray boxes b let !z = Set.union x y print $ Set.size z writeArray boxes a Set.empty writeArray boxes b z ``` なお、最初はボール集合とボール集合の結合なので Union-Find を使いましたが、これは間違ってました。 「Union-Find ? 楽勝じゃないか」 ![[スクリーンショット 2023-11-19 11.51.45.png|240]] 「あわわ、ボールが繋がりすぎる···」 ![[スクリーンショット 2023-11-19 11.51.28.png|300]] ところで Haskell の集合操作には Set と IntSet という二つの実装が、標準で提供されています。 整数しか扱わないなら、基本的には IntSet の方が速いです。が、一つ罠がありまして `size` が Set は $O(1)$ なのに IntSet は $O(n)$ なのです。 案の定それを忘れていて、最初に送信した実装が TLE になって焦るという事故もありました。 ---- ## 感想など 相変わらず、AtCoder Daily Training MEDIUM のバーチャル参加を一日一回こなすのを日課にしています。 実践に近い形式での精進を繰り返しているおかげで、問題文を読み取るスピードが早くなるとか、沼ったときのメンタルコントロールが上手になるとか、そういう経験値が溜まってきている感じがあります。 より難易度の高い問題を解くには、その手前でつまづかないようにする、というのが重要なのがよくわかりました。 おかげでここ数回は前半のスコアが安定していて後半の問題にじっくり取り組めています。 より難しい問題を解く、知識を蓄えるだけがトレーニングではない、というのはスポーツと同じだなあと思いました。 ところで、最近 PS5 を買って今更 PS5 のデモンズソウルをやってます。 デモンズソウルではボス戦などで緊迫した場面になると、緊張から、普段のようにキャラクターを操作できなくなる人も多いと思います。私も例に漏れずです。ボス戦で死ぬとそれまでに溜め込んだソウルが無駄になるし、何よりそのボスに辿り着くまでの道のりが長いこともあり、サンクコストが積もり積もっていて「ここで死ぬわけにはいかない」という意識が頭を占めるようになります。これが緊張のトリガーだと思います。 昨日もとあるボスに挑んだのですが、ボスと戦いながらふと「この緊張感、なんか競プロの本戦のときみたいだな」と思いました。 それで、本戦の時にメンタルをコントロールするような感じで深呼吸したり気楽に考えてみたりしたところ緊張が抜けて、普段通りに操作できるというか、それまで視野狭窄になっていてボスの動きをあまりよく見れてなかったのが、視界が開けて見えるようになりました。面白いものです。 真剣にメンタルトレーニングにでも行ってみようかなと思い始めました😎