# ABC345 振り返り - [モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345） - AtCoder](https://atcoder.jp/contests/abc345) - ABCD 4完 (1470) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc345) ![[スクリーンショット 2024-03-17 8.10.26.png]] ![[スクリーンショット 2024-03-17 8.10.55.png]] ABC345 でした。最近の中では高難度回でした。 TLE に苦しみながらもなんとか D を通して水色パフォーマンスを出すことができました。 アルゴリズムは合ってるのに TLE が取れないという直近2回と同じ状況になり「またか」と思いましたが、今回はなんとか脱出できました。 - A (灰) ··· `<====>` みたいになってるか判定。先頭、末尾、それ以外に分離して判定 - B (灰) ··· `ceildiv` - C (茶) ··· 全体の組み合わせ数は $_NC_2$ で、文字被りがある分をそこから引く。被りがあるとき $+1$ が必要な地雷あり - D (水) ··· マス目を集合で管理し、DFS で全タイルの敷き詰めを試す。枝刈りで、マスを埋められたらそこで切り上げる でした。 E、F ともに黄色難易度で少し考えてみましたが、全然わからずでした 😅 ## [A - Leftrightarrow](https://atcoder.jp/contests/abc345/tasks/abc345_a) 先頭、末尾、それ以外の文字が条件を満たしているかチェックします。 ```haskell main :: IO () main = do s <- getLine printYn $ head s == '<' && last s == '>' && all (== '=') (dropEnd 1 $ drop 1 s) ``` ## [B - Integer Division Returns](https://atcoder.jp/contests/abc345/tasks/abc345_b) ABC239 [B - Integer Division](https://atcoder.jp/contests/abc239/tasks/abc239_b) が床関数、今回は天井関数ですね。 こういうのは浮動小数点を使うとはまります。整数のまま計算できる `ceildiv` 関数を盆栽している私に死角はありません。 `ceildiv` は割とよく使いますね。 ```haskell main :: IO () main = do x <- getInt print $ x `ceildiv` 10 ceildiv :: Integral a => a -> a -> a ceildiv a b = (a + b - 1) `div` b ``` ## [C - One Time Swap](https://atcoder.jp/contests/abc345/tasks/abc345_c) 任意の二つの文字を $1$ 度だけ交換できるとき、何種類の文字列が作れるか? 勢いで適当に実装して送信したら2ペナもらってしまいました 😇 入力例 $1$ は `abc -> [bac, cba, acb]` となるわけですが、よくみると変換後のリストに元の文字列である `abc` がない、というところがポイントです。 一方、入力例 $2$ は `aaaaa -> [aaaaa]` と、元の文字列があります。 文字列中に記号の被りがある場合、同じ記号の入れ換えが発生するため、変換後にも元の文字列が登場することになります。 逆に被りがない場合は元の文字列は登場しません。 ここを分岐で切り分ける必要があります。 その上で、全体の組み合わせは $_NC_2$ 、ここから同じ記号同士を選ぶ組み合わせを取り除きます。 同じ記号同士の組み合わせ数は、バケットを作って $_nC_2$ すれば 求まります。 ```haskell main :: IO () main = do s <- getLine let n = length s n' = length $ nubOrd s bucket = toBucket ('a', 'z') s k = sum [nc2 i | i <- elems bucket, i >= 2] if n == n' then print $ nc2 n - k else print $ nc2 n - k + 1 ``` ## [D - Tiling](https://atcoder.jp/contests/abc345/tasks/abc345_d) 今回の山場です。この問題を解けるかどうかで勝敗が決まる回でした。 集合 + DFS で解きました。再帰による全探索です。 タイル部品が与えられて、それでマス目をぴったり埋めるという問題は ABC196 の [D - Hanjo](https://atcoder.jp/contests/abc196/tasks/abc196_d) という似た問題があります。 処理の構造的には、今回の問題と良く似ていて集合 + DFS で解けます。 今回はタイルの形状が様々あるので Hanjo よりもやや難しいですが、DFS の構造自体は同じだったのでそれを参考に組み立てて行きました。 - グリッドの各マスにタイルが置かれているかどうかを集合 (Set) で管理する - $(1, 1)$ から $(H, W)$ まで順番にみていく。これを現在地とする - まだ未使用のタイル部品を、現在地から試しに置いてみる。グリッドの集合とタイル部品の集合が疎 (disjoint) なら置ける。union でグリッドの集合にタイル部品の集合を合成することでタイルを消費し、現在地を次のマスに移す - 置けない場合 ··· すでに現在地マスが埋まっている場合はタイルは消費せず、現在地を次のマスに移す - 現在地がまだ埋まってないにも関わらずタイルを置くこともできない場合は、隙間ができることになるので再帰しない - $(H, W)$ まで全部見終わったところで、集合のサイズをチェックし、$H \times W$ ぴったりなら条件を満たす というのが方針です。 [TypeScriptでどこまで「関数型プログラミング」するか ─ 「手続き Haskell」から考察する - 一休.com Developers Blog](https://user-first.ikyu.co.jp/entry/2023/12/10/134411) にも寄稿したのですが、この手の DFS を宣言的に実装すると戻り値を呼び出し元に戻していくところの認知負荷が高く、しんどいです。 こういうときは戻り値を `()` にして、敢えて手続き型プログラミングすると楽です。 また、マスもタイルも集合で実装することで、タイルを置けるかどうかの判定は `Set.disjoint`、タイルを置く場合は `Set.union` で良いのでシンプルに記述できます。 ところで最初は State モナドを使って、マスを埋めることができたケース数を数えてそれが $0$ より大きかったら `Yes` ··· と枝刈りせず計算していました。 が、これは TLE してしまいました。83 個のテストケースのうち 81個が通って 2件が TLE でした。 この問題は「マスをぴったり埋められるかどうか」だけを問われているので、マスを埋められるケースが見つかったらそこで計算は停止してよいわけです。 大域脱出的な計算の切り上げは Haskell だとなかなか骨が折れるところですが、`exitSuccess` による強引な枝刈りを実装してみたところうまくいき 1.7 sec で通りました。 ```haskell dfs b _ s _ [] | rangeSize b == Set.size s = putStrLn "Yes" >> exitSuccess | otherwise = return () dfs b ts s xs (v@(i, j) : vs) | Set.member v s = dfs b ts s xs vs | otherwise = do for_ xs $ \x -> do let (di, dj) = ts VU.! x tileA = Set.fromDistinctAscList $ range ((i, j), (i + di - 1, j + dj - 1)) when (Set.disjoint s tileA) $ do dfs b ts (Set.union s tileA) (delete x xs) vs when (di /= dj) $ do let (di', dj') = swap (ts VU.! x) tileB = Set.fromDistinctAscList $ range ((i, j), (i + di' - 1, j + dj' - 1)) when (Set.disjoint s tileB) $ do dfs b ts (Set.union s tileB) (delete x xs) vs main :: IO () main = do [n, h, w] <- getInts xs <- replicateM n getTuple let ts = VU.fromList xs b = ((1, 1), (h, w)) vs = range b dfs b ts Set.empty [0 .. n - 1] vs putStrLn "No" ``` ### 最後のマスまで見なくてもいい リファクタリングしつつ 261 ms に縮めた実装が以下です。 元の実装では現在地を $(1, 1)$ から $(H, W)$ までしっかり見ていましたが、最後までみなくてもぴったりマスが埋まったところで切り上げてよいわけです。 ただしこの場合は、グリッドからはみだしてタイルを置けるケースを除外する必要があります。タイル部品の右下端がグリッドの境界を超えている場合は、そのタイルは置けないと判断します。 ```haskell dfs b _ s _ [] | rangeSize b == Set.size s = putStrLn "Yes" >> exitSuccess | otherwise = return () dfs b ts s xs (v : vs) | rangeSize b == Set.size s = putStrLn "Yes" >> exitSuccess | Set.member v s = dfs b ts s xs vs | otherwise = do for_ xs $ \x -> do let d = ts VU.! x ds = if fst d == snd d then [d] else [d, swap d] for_ ds $ \d -> do let tile = Set.fromDistinctAscList $ range (v, v + d - 1) when (inRange b (Set.findMax tile) && Set.disjoint s tile) $ dfs b ts (Set.union s tile) (delete x xs) vs main :: IO () main = do [n, h, w] <- getInts xs <- replicateM n getTuple let ts = VU.fromList xs b = ((1, 1), (h, w)) vs = range b dfs b ts Set.empty [0 .. n - 1] vs putStrLn "No" ``` ## 感想など 久し振りに水色パフォーマンスを取ることができました。 今回は問題を解く順序などの立ち振る舞いで水色という感じではなく、正面から D を解ききって腕力でもぎとった水色だったので、達成感がありました。 年末年始はどうにも調子が悪かったのですが 1月末くらいからスコアが安定してきて、今回良い成績をとることができました。 確実に実力がついてきているのを実感しました。 ここ最近の好調の要因は、何度か書いているとおり AtCoder Daily Training をコツコツやっていることだと思います。 昨日「科学的根拠に基づく最高の勉強法」という本を読みましたが、そこに書かれていた「インターリービング」という手法がこれを説明していると思いました。 かいつまんでいうと、スポーツの練習時に特定のスキルを集中的に練習する「ブロック練習」と、似たような複数のタスクを混ぜて練習する「ランダム練習」では、後者の方が学習効果が高いということです。練習した当人の主観ではブロック学習の方が学習効率が高いと感じるそうですが、実際にその後にテストを行ってみるとランダム学習を行った場合のほうが大差をつけて成績が良かったそうです。 よって、練習の際は似たようなタスクを複数組み合わせる手法が効果的。これがインターリービングです。 この際、それぞれのタスクにどんなスキルが必要か事前に分からない方がより良いそうです。 競プロに置き換えてみると、特定のアルゴリズムにテーマを決めて精進するよりも、バーチャル参加でランダムに問題を解く方が学習効果が高い、ということが言えそうです。 問題の難易度も特定の難易度に絞り込むと解法には偏りが生じるでしょうから、もしかすれば、難易度もある程度分散している方が良いのかも知れません。 (ただし、インターリービングには無関係なタスクを組み合わせても効果がが薄い、ある程度の前提知識をブロック学習で先にみにつけてからやったほうがいいなどの注意点もあるそうなので、興味がある方は書籍を読んでみて下さい。) AtCoder Daily Training のバーチャル参加には、明らかにこの辺りの効果があるように感じます。 詳細は割愛しますが、バーチャル参加を繰り返すのには「分散学習 」と「アクティブリコール」の効果も乗ってくると思います。 ただし「流暢性の錯覚」といって、単に簡単な問題をスラスラ問題を解けていることを練習がうまくいっていると錯覚してしまう現象があるのでこれには気をつけないといけません。脳に適切な負荷がかかっているかを冷静にレビューして、難易度を上げていく必要があります。 私の場合 AtCoder Daily Training の MEDIUM だと、やや負荷が足りなくなりつつあるので最近は過去の ABC にバーチャル参加するなどもしています。ADT に MEDIUM と HARD のちょうど中間ぐらいの難易度があるとなお嬉しいのですが...! そういえば、バチャを中心に練習して短期間で強くなった方、というとやはり mayocorn さんですね。 - [【AtCoder】中卒の主婦が青コーダーになったおはなし【競技プログラミング】 - Qiita](https://qiita.com/mayocorn/items/4edff486428240864808) 先の書籍を読んだ後に改めて mayocorn さんのこの記事を読んでみると、とても理にかなった練習方法だということがよく分かりました。 ···というわけで、引き続きバーチャル参加を中心に練習メニューを組み立てて、やっていこうと思います。 ---- # おまけ Haskell 精進記録 今週は盆栽が育つケースはあまりなかったです。 先週の ABC の E 問題を深掘りするために [[Haskell の IntMap vs HashMap]] を調べた、ぐらいですかね。