AtCoder Beginner Contest 136 F - Enclosed Points

解説

数え上げの軸を変える

$2^{N}-1$ 個の部分集合それぞれについて、その集合に対応する長方形に $N$ 個の点のうちいくつ含まれるかを考え、それを全て合計したものを求めよ。

という問題です。部分集合の数が多すぎますね。まともに列挙するのは到底無理です。

これをこうひっくり返します。

$N$ 個の点それぞれについて、長方形にそれが含まれるような部分集合が $2^{N}-1$ 個のうちいくつあるかを考え、それを全て合計したものを求めよ。

このように「XについてYを数えたものを合計する」を「YについてXを数えたものを合計する」と言い換えるのはとても重要なテクニックの1つです。特にXに当たるものが何かの選び方や並べ方だと、Xの要素数が $2^{N}$ や $N!$ など膨大になりがちです。Xの要素数が膨大でYの要素数が比較的小さい場合、ひっくり返すと見通しが良くなることが多いです。

点が長方形に含まれる条件を考える

ある1点 $P$ を見た時に、長方形に点 $P$ が含まれるような部分集合の個数を数えることを考えます。

まず $P$ 自身が部分集合に含まれるときは残りの点の選び方に関わらずOKです。残りの点を部分集合に含めるかどうかを自由に選べるので、場合の数は $2^{N-1}$ 通りです。

以降は $P$ を部分集合に含まない場合を考えます。このとき、長方形に点 $P$ が含まれる必要十分条件は、

点 $P$ から見て左上にある点と、右下にある点がともに1個以上選ばれている。
または、点 $P$ から見て右上にある点と、左下にある点がともに1個以上選ばれている。

この少なくとも一方が満たされることです。つまり座標平面を点 $P$ から見て左上・左下・右上・右下の4領域に分けて、それぞれの領域の点が1個以上選ばれているかどうかの組み合わせによって、長方形に点 $P$ が含まれるかどうかが決まります。

f:id:betrue12:20190805211133p:plain

図のようにそれぞれの領域に $A, B, C, D$ と名前を付け、「その領域に1個以上点が含まれている」という事象を同じ記号で表すことにします。またある事象 $X$ に当てはまる場合の数を $|X|$ と表記することにします。そうすると上記の条件を満たす場合の数は

$|(A\cap D) \cup (B\cap C)|$

となりますが、これは包除原理 $|X \cup Y| = |X| + |Y| - |X\cap Y|$ を用いて

$|A\cap D| + |B\cap C| - |A\cap B\cap C\cap D|$

と等しくなります。

これで「かつ」条件だけで求められる式になりました。それぞれの領域について点の選び方は実質的に独立に決めて良いので、各領域ごとにその領域に含まれる点の「全ての選び方の数」と「1個以上選ぶような選び方の数」を求めることができればこの場合の数を求めることができます。

※「実質的に独立に決めて良い」と書いたのは、問題文では「空でない」部分集合に限定しているので厳密には独立ではないという意味ですが、空集合は答えに算入しないと思うことにすればこれは考慮しなくて良いです。

※今回の問題では制約上、点 $P$ の真上・真下・真横に他の点が存在しないので、4領域が重複なくきれいに分かれるようになっています。やさしい。

それぞれの領域にある点を数える

ある領域に点が $k$ 個含まれているとき、全ての選び方は $2^{k}$ 通りあります。そのうち1通りだけが「1個も選ばない」というものなので、1個以上選ぶような選び方は $2^{k}-1$ 通りです。つまり、領域に含まれている点の個数が分かればよいです。

座標平面上の長方形領域に含まれる点の個数なので、座標圧縮して二次元累積和などが使えると良いのですが… $O(N^{2})$ かかってしまうので時間もメモリも足りません。何とかして一次元に潰したいです。

これは、点を調べていく順番を工夫することで解決できます。 $x$ 座標の小さい順に点を見ていくと、点 $(X, Y)$ を見ているときの領域それぞれは

既に見終わった点のうち、 $y \lt Y$ であるようなもの
既に見終わった点のうち、 $y \gt Y$ であるようなもの
まだ見ていない点のうち、 $y \lt Y$ であるようなもの
まだ見ていない点のうち、 $y \gt Y$ であるようなもの

として求めることができます。つまり具体的な $x$ 座標の値を考えなくても良くなり、 $y$ 座標だけの条件で計算できます。

あとは「既に見終わった点」「まだ見ていない点」のそれぞれについて、 $y$ がある範囲内にあるような点の個数を求めれば良いです。これはそれぞれについて $y$ 座標をインデックスとするようなBITを用意し、最初にBIT（未）に全ての点を入れておき、点を見ていくごとにBIT（未）から除外してBIT（既）に足す、という処理をしていけば実現できます。座標圧縮を忘れずに。

f:id:betrue12:20190805211850p:plain

これで各領域に含まれる点の個数を1回あたり $O(\log N)$ で求めることができたので、先ほどの計算式を用いて場合の数を求めることができます。全体計算量は $O(N\log N)$ になります。

ACコード

Submission #6701344 - AtCoder Beginner Contest 136

上記コードの細かい補足としては、BITで範囲を指定する時に点 $P$ の $y$ 座標も含めてしまっています（このBITは閉区間で作っています）。コードのように、点Pを見る前にBIT（未）から除いて見た後にBIT（既）に足すようにするとこれでもOKです。もちろん点 $P$ 自身の $y$ 座標を含めないように範囲指定してもOKで、そちらのほうが安全です。