Mo’s アルゴリズムについて勉強しました

3/11(土)のAtCoder Beginner Contest 293で、Mo'sアルゴリズムを使って解く問題が出題されました。

コンテスト中手も足も出ませんでしたので、該当の問題と過去問をいくつか解きました。

解いた問題

感想

AtCoder Beginner Contest 242に出題されてTwitterでも話題になっていたのを見かけましたが、その時に少し見たくらいで理解が全然できていませんでした。今回改めて座学とコード化とやって、次回出題されたときには使えるよう対策できたと思います。個人的には、クエリ平方分割を学んでおくと理解が早まりました。

解答コードはGoで書いたのですが、一部制限時間ギリギリのケースがありました。もしかしたら効率の悪い探索をしているかもしれませんので、この辺りは改めて調べておこうと思います。