競技プログラミング用知識集積所

ABC410F - Balanced Rectangles

最終更新：2025年06月15日 14:14

sport_programming

- view

管理者のみ編集可

問題
必要知識
考え方
解答例
注意点
- long long型を使う。
別解

問題

ABC410F

必要知識

B以下レベルの内容は省略

二次元累積和（未作成）

考え方

まず、愚直にO(H^4*W^4)かかるため、全然間に合わない。
そこで、まず単純な高速化として、個数チェックを二次元累積和（未作成）にする。
すなわち、#のマスを+1、.のマスを-1として、範囲内の総和が0になるか判定すればよい。
すると、4つの値の組み合わせが決まればそこから先はO(1)で判定ができる。

しかし、4つの値の組み合わせはほぼH^2*W^2個あるため、それでもまだ間に合わない。
さらなる高速化を考える。

上下の境界は普通に全探索（未作成）するとして、左右方向を工夫する。
二次元累積和（未作成）による矩形領域の総和は「右下-右上-左下+左上」と求める。
これを「（右下-右上）-（左下-左上）」だと思ってやる。
すると、これが0になるというのは「右下-右上 == 左下-左上」が成り立つということである。
したがって、各列について指定行の「上-下」を計算し、その値が一致するペアの個数を数える問題になる。

これには各値が何回登場したかを数えておき、その後、個数*(個数-1)/2の足していけばよい。
各値が何回登場したかのカウントは超基本的な典型問題……と見せかけて、ここがこの問題の最大の難所。
これにはいくつかの方法があり、

全部をvector（未作成）に突っ込んでソートし、前から順に見ていく
map（未作成）を使ってカウントする
vector（未作成）を使ってカウンティング（未作成）していく

などが使えそうに見える。
間に合うかどうか、順に考えてみる。

まず、全部をvector（未作成）に突っ込んでソートし、前から順に見ていくやつ。
大きさがWのvector（未作成）をソートするには、O(W*logW)かかる。
つまり、全体でO(H^2*W*logW)かかる。
これは面積300000のほぼ正方形の場合に1.03*10^9ほどになり、ループ内がよほど高速でなければ厳しい。
誤答例のつもりが、間に合ってしまったやつ

次に、map（未作成）を使ってカウントする。
これも結局、全体でO(H^2*W*logW)かかるため、同じようにダメ。
unordered_mapを使えば全体がO(H^2*W)で済み、面積300000のほぼ正方形の場合1.6*10^8になるので、3秒なら間に合いそうに見える。
しかし、unordered_mapは定数倍が遅いため、ギリギリ間に合わない。
誤答例（2TLE）

最後に、vector（未作成）を使ってカウンティング（未作成）していく方法。
今回取りうる値は-H*WからH*Wまで2*H*W+1通りなので、これを毎回用意すると全体がO(H^3*W)になって全然ダメ。
また、使いまわすにしても、カウント後の処理でvector（未作成）の値を全部見るとダメだし、リセットするのも全部見るとダメ。
そこで、カウンティングが終わった後でもう一度vector（未作成）の中身を見ながら、変更があった場所だけ計上とゼロ戻しをしていくことにする。
これにより全体がO(H^2*W)で済み、面積300000のほぼ正方形の場合1.6*10^8で間に合う。
もちろんH<Wの場合も同じ方法で間に合う。

残る問題はH>Wだった場合だが、これはHとWの立場を入れ替えて実行すればよい。
同じようなコードを2回書くよりは、H>Wだったら対角線反転する方が楽。