■「ねえ、この問題の解き方って分かる？」
●「”Count The Rectangles“…… Educational Codeforces ですか。私、えでゅふぉは参加したことないんですよね」
■「僕もリアルタイムで参加したことはないんだけど、過去問を解こうかなと思ったら、この問題が解けなくて」
●「先輩は解説見たんですか？」
■「一応見たんだけど、こういう問題が苦手で、どう思いつけばいいのか分からないんだよね」
●「なるほど…… とりあえず見てみますね」
Count The Rectangles
概要
●「二次元平面上に存在する、縦か横の線分がたくさん与えられて、そのうち4本選んで長方形を作る問題ですね。答えるのは長方形の数、つまり長方形を形成するような4本の辺の選び方の数ですね」
■「うん。長方形を作るには、縦線 2 本と横線 4 本が 4 つの交点を持てば良くて、角ははみ出していてもいいというルールだね」
●「線の数が 5000 以下なので、縦横 2500 ずつでも、答えの最大値は ${}_{2500}\text{C}_{2}\times {}_{2500}\text{C}_{2}$ なので、long long の範囲には収まりますね」
■「int だとオーバーフローする場合があるから注意しないとね」
●「座標は [-5000, 5000] の範囲なので、計算量としては $O(N^2\log N)$ や $O((\text{片方の座標の範囲}\times N\log N))$ が間に合いそうですね。全座標だと $10000^2$ になるのでちょっと不安ですかね」
■「サンプル 1 の図はこうだね。答えは 7 。確かに、7 つの長方形が作れるね」
●「サンプル 2 はこうですけど、途切れているので長方形は作れませんね」
考察
●「答えとしてあり得る値が $O(N^4)$ で int に収まらない大きさなので、一つずつ数えるのはもちろんダメですよね」
■「そうだね。効率的に数えないといけないね」
●「となると、複数個をまとめて考えたい気持ちになりますね…… 例えば、上下の辺を固定すれば、両方に交わる縦線の中から 2 本選ぶ方法を数えるだけなので、${}_n\text{C}_2$ で計算できますよね」
■「そうすると、一回で $O(N^2)$ の個数をまとめて計算できるので、必要な計算回数が $O(N^2)$ 回程度になりそうだね」
●「ただ、上下の辺を決めても、両方に交わる縦線を数えるのが $O(1)$ ではできなさそうなんですよね…… x 座標だけ記録しておけば、セグメントツリーやBIT で区間和の計算として $O(\log x\text{座標の範囲})$ になるので、そうしたいんですけど……」
■「なるほど、そう考えていくのか」
●「とりあえず思いつく方針は、走査線を使う方法ですかね。上下を固定する方法にするかは分かりませんが、どっちにしても走査線を使うことになりそうな……」
■「走査線ってどうやるの？」
●「y=-5000 の直線部分に注目して、その注目部分を少しずつ上に上げていくイメージですね」
■「具体的にどうやって計算するの？」
●「走査線（注目する y 座標を示す線）を -5000 から上に上げていきながら、“有効な縦線” を記録しておきます。”有効な縦線” というのは、“下の方で横線を交わっているため、新たな横線と交われば長方形を作れる縦線の x 座標” です。図にするとこうなります」
●「サンプル 1 の例では、y=-1 まではずっと有効な縦線なしです。それまで横線がないので」
■「y=-1 になったら、線分 (-2, -1, 4, -1) と交わる縦線の x 座標が “有効な縦線” に追加されるんだね」
●「はい。また、y=2 を超えても、x=5 は追加されません。この縦線はまだ横線と交わっていないので」
■「y=3 になったら、新たな横線が見つかるね。このときはどうなるの？」
●「このときは、横線の x 座標の範囲が [1, 5] なので、“有効な縦線” の x 座標のうち、ここに含まれる（つまりこの横線を交わる）ものを数えます。今回は 2 本ですね。この場合、2 本の中から 2 本を選ぶことで長方形を作れるので、${}_2\text{C}_2=1$ 通りの長方形を作れます。この値を答えに足します」
■「なるほど。そして、y=3 を過ぎたら “有効な縦線” に 5 が追加されているんだね」
●「はい。そして、先程と同様に、y=4 に達したら横線 [-2, 6] と交わる縦線の数を数えて、2 本選ぶ方法を答えに足します」
■「今回は ${}_4\text{C}_2=6$ だね。これとさっきの値を合わせて 7 だね」
●「はい。走査線の移動が 10000 回、一回の計算に高々 N 回なので、計算量も間に合います。ただ、サンプル 1 の場合は答えが合うんですけど、ダメな例もありますね」
■「どういう場合？」
●「こんなときです」
■「なるほど、この場合、上の横線まで来たときの “有効な縦線” を {0, 2, 3, 5} の 4 本にするとまずいんだね」
●「はい。4 本の x 座標だけ記録しておくと、上の横線で ${}_4\text{C}_2=6$ 通り足してしまいます。実際は、内側 2 本と外側 2 本の 2 通りの選び方しか条件を満たさないので、2 通りですね」
■「そうか、じゃあどうしたらいいんだろう」
●「“有効な縦線” を、対象の横線ごとに管理すれば大丈夫ですかね？」
■「対象の横線ごとに管理？」
●「こういうイメージです」
■「なるほど。こうして、各グループごとに、その中から 2 本選ぶ方法を計算するんだね。これで ${}_2\text{C}_2+{}_2\text{C}_2=2$ だね。計算量は大丈夫かな？」
●「走査線を走らせるのに 10001 回で、一回ごとに以下の計算を行うわけですよね」
- 走査線の y 座標に横線 h がある場合（h を上辺とする長方形を数える）
- h と交わる縦線の x 座標を、h 対応する “有効な縦線”グループ に追加
- h より下の横線（下辺の候補）に対応する全グループに対し、h の x 座標の範囲内の値の個数 n を数え、${}_n\text{C}_2$ （左右辺の選び方）を答えに足す
- 走査線の y 座標に上端がある縦線の x 座標を全グループから消す
■「この計算が $O(N\log N)$ くらいに収まれば大丈夫そうだね」
●「はい。今回は、(1.1) の計算で全ての縦線を見るので $O(N)$、(1.2) の計算では、各横線グループに対して セグメントツリーや BIT (Binary Indexed Tree) を持っておけば、区間和の計算として $O(N\log (x\text{座標の範囲}))$ で計算できます」
■「セグメントツリーや BIT を、横線の数だけ持つってこと？」
●「はい。セグメントツリーや BIT の配列の長さが 10001 で、個数が 5000 以下なのでメモリが少し不安ですね」
■「ということは、(1.1) の計算では、横線 h と交わる縦線の x 座標について、横線 h に対応するセグメントツリーや BIT の位置を 1 に変えるってことだね」
●「はい。(2) の計算は、削除セット set<int> del[10001] を用意しておき、(1.1) の段階で追加した縦線の上端 y と x 座標について、del[y].insert(x) を行います」
■「del[y] は int の集合なんだね。どういう意味なの？」
●「del[y] は 走査線が y を超えるときに全横線のグループから削除すべき x 座標の集合を表します。例えば下の状態であれば、del[3]={4}, del[4]={-1, 2} になります」
■「うーん、ちょっとややこしいね」
●「もうちょっとコードっぽく処理を書くとこうなります。線分は構造体 struct segment{int x1, x2, y1, y2}; とします」
- 入力受け。座標は [0, 10000] にしておく。横線 (horizontal) と縦線(vertical) で分けて記録。座標は x1<=x2, y1<=y2 になるように必要なら入れ替え。
- 横線を y 座標でソート
- 次に見る横線のインデックス h_index を 0 にしておく。
- 答えを入れる ans も 0 にしておく
- 横線の数だけ BIT を用意（bit[i] が横線 i に対応）。サイズ 10001 、全て 0 初期化
- 削除用セット set<int> del[10001] を用意。
- 走査線の位置 y について、0 から 10000 までループ（h = horizontal[h_index] とする）
- h_index < 横線数 かつ horizontal[h_index].y1 == y なら横線の処理
- 全ての縦線 v について、v が h と交わるなら、bit[h_index] の v.x1 要素に 1 を足す
- del[v.y2] の集合に v.x1 を追加する
- h 以下の横線についてループ（添字 i を 0 から h_index-1 まで）
- bit[i] の [h.x1, h.x2] の区間和を n とする
- ans に n*(n-1)/2 を足す
- h_index を 1 増やす
- h_index < 横線数 かつ horizontal[h_index].y1 == y なら横線の処理
- del[y] に含まれる値 x についてループ
- 添字 i を 0 から h_index – 1 までループ
- bit[i] の x における値が 1 なら 1 減らす
- 添字 i を 0 から h_index – 1 までループ
- ans を出力する
■「へー、横線を y 座標でソートしておくことで、走査線に重なる横線を探す処理で 毎回$O(N)$ かからないようにしてあるんだね。(7.1, 7.2, 7.3) の処理は、h_index が毎回増えるから最大でも N 回しか行われないね」
提出
●「コードはこうなりますね。とりあえずサンプルは合ったので、提出してみましょう」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
#include <algorithm> #include <iostream> #include <set> #include <vector> using namespace std; #define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) repr(i, 0, n) // Binary Indexed Tree （区間和） struct BIT { int n, height; vector<int> data; BIT(int _n) { n = 1; while (n < _n) { n *= 2; } data = vector<int>(n + 1, 0); } // [0,i) の和 int sum(int i) { int s = 0; while (i > 0) { s += data[i]; i -= i & -i; // i & -i は i の最後の1ビット } return s; } // 場所 i に値 x を足す void add(int i, int x) { i++; while (i <= n) { data[i] += x; i += i & -i; } } // 添字でアクセス long long operator[](int i) { return sum(i + 1) - sum(i); } }; // 線分を表す構造体 struct segment { int x1, y1, x2, y2; }; int main(void) { int N; cin >> N; // 横線と縦線 vector<segment> horizontal, vertical; rep(i, N) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; // 負の座標が面倒なので [0, 10000] の範囲にする x1 += 5000; y1 += 5000; x2 += 5000; y2 += 5000; if (x1 > x2) swap(x1, x2); // x1 <= x2 にする if (y1 > y2) swap(y1, y2); // y1 <= y2 にする // 縦線と横線に分けて記録 if (x1 == x2) { vertical.push_back(segment{x1, y1, x2, y2}); } else { horizontal.push_back(segment{x1, y1, x2, y2}); } } // 横線を y 座標でソート sort(horizontal.begin(), horizontal.end(), [](segment a, segment b) { return a.y1 < b.y1; }); long long ans = 0; int h_index = 0; vector<BIT> bit(horizontal.size(), BIT(10001)); vector<set<int>> del(10001); rep(y, 10001) { while (h_index < horizontal.size() && horizontal[h_index].y1 == y) { segment h = horizontal[h_index]; // 走査線と重なる横線 h について処理 for (auto v : vertical) { if (h.x1 <= v.x1 && v.x1 <= h.x2 && v.y1 <= h.y1 && h.y1 <= v.y2) { // v は h と交わる bit[h_index].add(v.x1, 1); // v の x 座標を 1 にする del[v.y2].insert( v.x1); // v の上端に来たときに x 座標の値を消す } } // h 以下の線についてループ rep(i, h_index) { // horizontal[i] を下辺とする長方形を作る方法の数を計算 int n = bit[i].sum(h.x2 + 1) - bit[i].sum(h.x1); ans += n * (n - 1) / 2; } h_index++; } for (auto x : del[y]) { // 消すべき x 座標を全 BIT から消す rep(i, h_index) { if (bit[i][x] == 1) { bit[i].add(x, -1); } } } } cout << ans << endl; return 0; } |
■「あれ、5 つ目のテストケースで MLE だよ」
●「本当ですね。一番メモリを食いそうなのはどこでしょうか…… やっぱり BIT ですよね」
■「どうする？」
●「うーん、例えば、全部横線だけみたいな場合に、BIT は 5000 個用意されるんですけど、その場合は縦線が無いので、横線と縦線の少ない方に合わせればメモリは減らせますね」
■「それって面倒じゃない？」
●「いえ、横線が多い場合に x 座標と y 座標を入れ替えてあげれば大丈夫ですよ。その場合でも答えは変わらないですし」
■「なるほど。じゃあこんな感じかな」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
#include <algorithm> #include <iostream> #include <set> #include <vector> using namespace std; #define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) repr(i, 0, n) // Binary Indexed Tree （区間和） struct BIT { int n, height; vector<int> data; BIT(int _n) { n = 1; while (n < _n) { n *= 2; } data = vector<int>(n + 1, 0); } // [0,i) の和 int sum(int i) { int s = 0; while (i > 0) { s += data[i]; i -= i & -i; // i & -i は i の最後の1ビット } return s; } // 場所 i に値 x を足す void add(int i, int x) { i++; while (i <= n) { data[i] += x; i += i & -i; } } // 添字でアクセス long long operator[](int i) { return sum(i + 1) - sum(i); } }; // 線分を表す構造体 struct segment { int x1, y1, x2, y2; }; int main(void) { int N; cin >> N; // 横線と縦線 vector<segment> horizontal, vertical; rep(i, N) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; // 負の座標が面倒なので [0, 10000] の範囲にする x1 += 5000; y1 += 5000; x2 += 5000; y2 += 5000; if (x1 > x2) swap(x1, x2); // x1 <= x2 にする if (y1 > y2) swap(y1, y2); // y1 <= y2 にする // 縦線と横線に分けて記録 if (x1 == x2) { vertical.push_back(segment{x1, y1, x2, y2}); } else { horizontal.push_back(segment{x1, y1, x2, y2}); } } // 横線の方が多い場合、x 座標と y 座標を入れ替える（ MLE 対策） if (horizontal.size() > vertical.size()) { swap(horizontal, vertical); for (auto &s : horizontal) { s = segment{s.y1, s.x1, s.y2, s.x2}; } for (auto &s : vertical) { s = segment{s.y1, s.x1, s.y2, s.x2}; } } // 横線を y 座標でソート sort(horizontal.begin(), horizontal.end(), [](segment a, segment b) { return a.y1 < b.y1; }); long long ans = 0; int h_index = 0; vector<BIT> bit(horizontal.size(), BIT(10001)); vector<set<int>> del(10001); rep(y, 10001) { while (h_index < horizontal.size() && horizontal[h_index].y1 == y) { segment h = horizontal[h_index]; // 走査線と重なる横線 h について処理 for (auto v : vertical) { if (h.x1 <= v.x1 && v.x1 <= h.x2 && v.y1 <= h.y1 && h.y1 <= v.y2) { // v は h と交わる bit[h_index].add(v.x1, 1); // v の x 座標を 1 にする del[v.y2].insert( v.x1); // v の上端に来たときに x 座標の値を消す } } // h 以下の線についてループ rep(i, h_index) { // horizontal[i] を下辺とする長方形を作る方法の数を計算 int n = bit[i].sum(h.x2 + 1) - bit[i].sum(h.x1); ans += n * (n - 1) / 2; } h_index++; } for (auto x : del[y]) { // 消すべき x 座標を全 BIT から消す rep(i, h_index) { if (bit[i][x] == 1) { bit[i].add(x, -1); } } } } cout << ans << endl; return 0; } |
●「これで提出して…… 時間がかかってますね…… やった、AC です！」
■「おおー。すごいね。解説ではたしか、下辺を決めてたけど、こんな方法でも解けるんだね」
●「解説では下辺固定ですか。なるほど、そっちも考えてみましょうか」
■「え、大変じゃない？」
●「いや、今回の方法をそう変わらないですよ。まず、下辺と交わる縦線を列挙して上端をメモして、下辺から走査線を上げていけばいいんです。こうすれば、BIT を複数持つ必要がなくなるので、 MLE の心配も無さそうですね」
■「そうか、”有効な縦線” を 1 つの集合として持つときに発生した問題がなくなるんだね」
●「はい。実装はこんな感じでしょうか。下辺の添字 h_index を決めて、その横線を下辺とする長方形を数える関数 scan() を用意しています」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include <algorithm> #include <iostream> #include <vector> using namespace std; #define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) repr(i, 0, n) // Binary Indexed Tree （区間和） struct BIT { int n, height; vector<int> dat; BIT(int _n) { n = 1; height = 1; while (n < _n) { n *= 2; height++; } dat = vector<int>(n + 1, 0); } // [0,i)までの和 int sum(int i) { int s = 0; while (i > 0) { s += dat[i]; i -= i & -i; // i & -i は i の最後の1ビット } return s; } void add(int i, int x) { i++; while (i <= n) { dat[i] += x; i += i & -i; } } }; struct segment { int x1, y1, x2, y2; }; vector<segment> horizontal, vertical; // horizontal[h_index] を下辺とする長方形の数を走査線で計算 long long scan(int h_index) { segment h = horizontal[h_index]; BIT bit(10001); vector<vector<int>> del(10001); // h と交わる縦線を記録 for (auto v : vertical) { if (h.x1 <= v.x1 && v.x1 <= h.x2 && v.y1 <= h.y1 && h.y1 <= v.y2) { // v は h と交わる bit.add(v.x1, 1); del[v.y2].push_back(v.x1); } } long long ans = 0; // 走査線を上に動かす repr(i, h_index + 1, horizontal.size()) { if (horizontal[i].y1 == h.y1) continue; // ここまでに消すべき x 座標を消す repr(y, horizontal[i - 1].y1, horizontal[i].y1) { for (auto x : del[y]) { bit.add(x, -1); } } // 交わる縦線を数える int n = bit.sum(horizontal[i].x2 + 1) - bit.sum(horizontal[i].x1); ans += n * (n - 1) / 2; } return ans; } int main(void) { int N; cin >> N; rep(i, N) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1 += 5000; y1 += 5000; x2 += 5000; y2 += 5000; if (x1 > x2) swap(x1, x2); if (y1 > y2) swap(y1, y2); assert(x1 <= x2 && y1 <= y2); if (x1 == x2) { vertical.push_back(segment{x1, y1, x2, y2}); } else { horizontal.push_back(segment{x1, y1, x2, y2}); } } sort(horizontal.begin(), horizontal.end(), [](segment a, segment b) { return a.y1 < b.y1; }); long long ans = 0; rep(i, horizontal.size()) { ans += scan(i); } cout << ans << endl; return 0; } |
■「こっちの方がシンプルだね」
●「関数化できるとコードが簡潔になっていいですね。走査線の上げ方も変えてみました。こっちは、横線を下から順にたどりながら、そこまでに消すべき x 座標を消す方法です。走査線を必要なところまで一気に上げるイメージですね。もちろん、横線を y 座標でソートしておかないと大変なことになります」
■「このコードでも AC だね」
●「走査線に慣れていない場合は、後のやり方の方が考えやすいかもですね」
■「いやー、難しいね。こういう問題の解法がなかなか思いつかないんだよね」
●「私も走査線を使う問題はあまり解いたことがなくて、まだ自分のものにできていないです」
■「でも思いつくんだからすごいなあ」
●「今回はたまたま最初に思いついた方針が正解だったというか…… 計算を省略したい気持ちで “使える縦線の中から 2 本選ぶ方法” でまとめて計算するのは定石ですよね。そこから、“使える縦線” を毎回全探索してたらダメっぽいので、差分だけ更新したい気持ちになって、どうやって状態を保持してどういう順番で更新しようか……と考えると走査線の発想に至りました」
■「なるほど、“まとめて計算”、”差分だけ更新”、”差分が少なくなるような更新順序” か。そう言われると、走査線に行き着くのは必然に思えてきてしまうなあ」
●「たくさん問題を解いて、こういうパターンを蓄積していきたいですね」