AtCoder Beginner Contest 242

 　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 242 DEで苦戦し、Eまで五完で終了。
B ソート
C DP
D tかkが0になるまで巻き戻して計算。難しい。
E 桁DPっぽく。バグらせて愚直を書いた。
G 平方分割だと思って実装を始めたが途中で詰まった。平方分割を使うのは正しかったようだがACできず。

— titia (@titia_til) March 5, 2022

F - Black and White Rooks

　解説放送を見てAC。

　コンテスト中、包除原理だと思ったが、詰められる気がしなかった（及び、Gの方がAC人数が多かった）ため飛ばした。

　意外とシンプルな包除で、多分解説を見なくても解けたと思う。

　解説を見ても何を前計算ができるかピンと来ず、毎回包除をやるのだから八乗になってしまうのでは？　と思ったが、自分で書いて見たら納得できました。こういうのは実際書いてみた方が分かりやすいですね。

　あと混乱していたのは、包除原理で「黒が使う行がk1行, 列がl1列。白が使う行がk2行, 列がl2列の場合の数」を求めるとき、そのk1, k2, l1, l2が小さいバージョンの答えを使う（それらを除いていく）のか？　と考えたこと。

（公式解説を見るとこれでも解けた模様。公式解説の「1. 動的計画法による解法」ですね。なんかこの方法も包除原理の一種と思っていた気もするけど、「これは包除原理じゃない」ということを頭に叩き込みたい）

　包除原理でそれは使わないのですね。

　「黒が使う行がk1以下, 列がl1以下。白が使う行がk2以下, 列がl2以下の場合の数」というものたちだけから「黒が使う行がk1行, 列がl1列。白が使う行がk2行, 列がl2列の場合の数」を求められる、というのが包除原理なのですね。

G - Range Pairing Query

　解説放送を見てAC。

　Mo’s algorithmは平方分割の一種と思っていたのですが、具体的には理解していませんでした。「二次元のクエリを先読み＆平方分割」と思って良いのかな。

　二次元クエリを平面上にプロットしてみると分かりやすかった。二つパラメーターがあるとき、困ったら平面にプロットしてみるのは鉄板ですね。

　参考：昔のMo’s algorithmの問題