L - Colorful Quadrilateral 解説
by 
tatyam
0. 定義
- \(2\) 次元ベクトル \(\overrightarrow{u}, \overrightarrow{v}\) に対し、外積を \(\overrightarrow{u} \times\overrightarrow{v} := u_xv_y - v_xu_y\) と定義します。
- \(2\) 次元ベクトル \(\overrightarrow{v}\) に対し、反時計回りに \(90^\circ\) 度回転させたベクトルを \(\text{rot}(\overrightarrow{v}) := \overrightarrow{(-v_y, v_x)}\) と定義します。
- \(2\) 次元ベクトル \(\overrightarrow{v}\) に対し、大きさ \(4\) の点集合 \(\text{top4}(\overrightarrow{v})\) を以下のように定義します。
- 各色 \(c\) について、色 \(c\) の点の中で \(\overrightarrow{v}\) との内積が最大である点を選出する。選出された点の中で、\(\overrightarrow{v}\) との内積が大きい \(4\) 点を \(\text{top4}(\overrightarrow{v})\) とする。
1. 答えとなる四角形の特徴
答えとなる四角形を四角形 \(ABCD\) とします。ここで、\(ABCD\) のうち \(2\) 点 \(A, C\) のみが分かっている状況を考えます。このとき、点 \(B, D\) は以下のように決定することができます。
- 点 \(A, C\) と同じ色の点は無視して考える。
- \(\overrightarrow{v} := \text{rot}(\overrightarrow{AC})\) と定義する。\(\overrightarrow{v}\) との内積が最小の点を \(B\)、最大の点を \(D\) とする。
- \(B\) と \(D\) の色が同じ場合は、その色を無視したときの最小 / 最大の点に、どちらか一方を変更する。(面積が最大になるように選ぶ。)
- 自己交叉がない場合、四角形 \(ABCD\) の面積は \(\dfrac12(\overrightarrow{AC} \times \overrightarrow{BD})\) と一致する。自己交叉がある場合、点 \(A, B, C, D\) の入れ替えでより大きな自己交叉のない四角形を作ることができるので、暫定的に面積を \(\dfrac12(\overrightarrow{AC} \times \overrightarrow{BD})\) として問題ない。
ステップ 2–3 の取り方から、以下の事実が分かります。
- 各色 \(c\) について、色が \(c\) である点集合を \(P_c\) とする。\(P_c\) の凸包の頂点となっていない点は、答えに選ばれることがない。
- 答えに選ばれている点 \(X\) に対して、ある方向 \(\overrightarrow{v}\) が存在して、\(X\) は \(\text{top4}(\overrightarrow{v})\) に含まれる。
2. \(O(N^3)\) 時間の解法
- 点 \(A, C\) を全探索します。
- \(\overrightarrow{v} := \text{rot}(\overrightarrow{AC})\) との内積の最小 / 最大 によって、点 \(B, D\) を \(O(N)\) 時間で決定します。
3. ある色でない点のうち、ある方向に最も大きいものを高速に見つける方法
セグ木状のデータ構造により、色が \(L, L+1, \dots, R-1\) のいずれかである点のうち、方向 \(\overrightarrow{v}\) との内積が最大であるものを \(O((\log N)^2)\) 時間で発見することができます。
具体的には、セグ木の各ノードに区間 \(A_l, A_{l+1}, \dots, A_{r-1}\) のモノイド積を入れる代わりに、色 \(l, l+1, \dots, r-1\) の点集合の凸包を入れることにします。 区間 \([L, R)\) が \(O(\log N)\) 個のセグ木のノード \([l_1, r_1), [l_2, r_2), \dots\) に分解される場合、各ノードで方向 \(\overrightarrow{v}\) との内積が最大である点を \(O(\log N)\) 時間で求め、それを集約すれば、全体で \(O((\log N)^2)\) 時間 / クエリ となります。
与えられる方向 \(\overrightarrow{v}\) がソート済みである場合は、方向 \(\overrightarrow{v}\) との内積が最大である点が変化するタイミングを計算しておき、セグ木の各ノードに \(\overrightarrow{v}\) との内積が最大である点を持たせることで、\(Q\) クエリを \(O((N + Q) \log N)\) 時間で処理することができます。
4. \(O(N^2 \log N)\) 時間の解法
- 点 \(A, C\) の組を全探索してベクトル \(\overrightarrow{AC}\) を列挙し、これらを \(O(N^2 \log N)\) 時間で偏角ソートします。
- 各 \(\overrightarrow{AC}\) に対し、点 \(A, C\) の色と異なる点のうち \(\overrightarrow{v} := \text{rot}(\overrightarrow{AC})\) との内積が最小・最大の点 \(B, D\) を、3. の方法でならし \(O(\log N)\) 時間で求めます。
- \(B, D\) の色が同じ場合は、\(B\) か \(D\) のどちらかを選び直します。(面積が最大になるようにします。)
5. 色が \(4\) 色しかない場合
色が \(4\) 色しかない場合を考えます。
一般性を失わず、点 \(A, B, C, D\) の色がそれぞれ \(1, 2, 3, 4\) であるとします。
ベクトル \(\overrightarrow{AC}\) の方向を \(\overrightarrow{v}\) とすると、
- 色 \(2\) で \(-\text{rot}(\overrightarrow{v})\) との内積が最大の点が \(B\)
- 色 \(4\) で \(\text{rot}(\overrightarrow{v})\) との内積が最大の点が \(D\)
となります。
注意
- 色 $1$ で $-\overrightarrow{v}$ との内積が最大の点が $A$
- 色 $3$ で $\overrightarrow{v}$ との内積が最大の点が $C$
したがって、以下のアルゴリズムで \(O(N \log N)\) 時間で解くことができます。
- 点集合を \(x\) 座標でソートする。
- \(O(N)\) 時間で、各色の凸包を取り、内部の点を削除する。
- 点 \(A\) の色を \(1\) とし、点 \(C\) の色を全探索する。
- 目標ベクトル \(\overrightarrow{v}\) を \(360^\circ\) にわたって回転させながらベクトル \(\overrightarrow{BD}\) の候補を列挙し、これらを偏角ソートする。
- この操作は、\(B\) の色の凸包の \(-1\) 倍と \(D\) の色の凸包のミンコフスキー和を取る操作に相当するから、\(O(N)\) 時間でできる。
- ベクトルを \(-1\) 倍したものも \(\overrightarrow{BD}\) の候補に入れることで、\(B\) と \(D\) の色が入れ替わったものも考慮に入れることができる。
- 同様に、ベクトル \(\overrightarrow{AC}\) の候補を列挙し、これらを偏角ソートする。
- ベクトル \(\overrightarrow{AC}\) の候補を走査し、それに対して面積が最大となるベクトル \(\overrightarrow{BD}\) を尺取り法で探して、面積 \(|\overrightarrow{AC} \times \overrightarrow{BD}|\) を計算する。
6. 乱択解法
色が \(4\) 色より多くある場合も、ランダムに色の写像 \(C : \{1, 2, \dots, N\} \to \{1, 2, 3, 4\}\) を取って \(4\) 色にした後上のアルゴリズムを適用することで、\(\dfrac{1}{32}\) の確率で正しく面積最大の四角形を計算することができます。したがって、これを何度か繰り返すことで、十分高い確率で答えを求めることができます。
驚くべきことに、繰り返す必要のある部分はすべて \(O(N)\) 時間で計算できるため、このアルゴリズムは、繰り返し回数を \(R\) として \(O(N \log N + RN)\) 時間で動作します。
しかし、この問題はマルチテストケースであるため、乱択解のみでの AC は難しいです。
\(N\) が小さいときは \(O(N^3)\) 解、\(N\) が大きいときは乱択解と使い分けた場合は AC を取ることができるかもしれません。
7. \(\text{top4}(\overrightarrow{v})\) の種類数について
決定的で高速なアルゴリズムを得るために、\(\overrightarrow{v}\) を一周させたときの \(\text{top4}(\overrightarrow{v})\) の種類数について考えてみましょう。色がすべて異なる場合は、order-\(k\) ボロノイ図 (最も近い点 \(k\) 個がどこかによって平面を分割した図) の領域の個数が \(O(k(N - k))\) 個であることから、\(O(N)\) 種類であることが従います。( \(k = 4\) または \(k = N-4\) を代入し、無限遠がどの領域に属するかを見れば良い)
色が一般の場合でも \(O(N)\) 種類であることが予想でき、実際にこれは正しいです。
証明
top4 の色としてあり得るものが $7N$ 種類以下であることが証明できれば、$\text{top4}(\overrightarrow{v})$ の種類数は $8N$ 以下であることが分かります。
$\text{top4}(\overrightarrow{v})$ の第 $4$ 位の点がある点 $p$ であるとします。 「第 $4$ 位の点が $p$ であるような $\text{top4}(\overrightarrow{v})$」は、「点 $p$ を境界で含む半平面 $\overrightarrow{v} \cdot \overrightarrow{x} \ge \overrightarrow{v} \cdot \overrightarrow{p}$ (ちょうど $4$ 色が含まれる)」に対応させることができます。
各点 $p$ に対し、「点 $p$ を境界で含む半平面がちょうど $4$ 色を含むとき、含む色の集合としてあり得るもの」は高々 $7$ 種類 (点 $p$ と同じ色の点が他にもあれば、それらの点を含むものを除外でき、高々 $4$ 種類) であるので、top4 の色としてあり得るものが $7N$ 種類以下であることが分かります。(実際には $2N$ 種類とかで抑えられると思います。)
「点 $p$ を境界で含む半平面がちょうど $4$ 色を含むとき、含む色の集合としてあり得るもの」の種類数について
考えるべきは、点 $p$ を境界で含む半平面を、点 $p$ を中心に回転させるときの、半平面に含まれる色の変化です。
まずは、点 $p$ と同じ色の点が他に存在し、これらを含んではいけない場合を考えます。この場合、半平面が回転できる範囲は $180^\circ$ 以下となります。
このときに、半平面を端から端まで回転させることを考えます。回転の途中で追加された色が削除されることはありませんから、色の個数がちょうど $4$ 色となるときの色の組み合わせは高々 $4$ 通りです。
$360^\circ$ 回転できる場合は、左右に $180^\circ$ の回転と見ることで、高々 $7$ 通りであることが分かります。
8. 準線形解法
以下のアルゴリズムを考えます。
- 各色の凸包を取り、内部の点を削除する。
- 目標ベクトル \(\overrightarrow{v}\) を \(360^\circ\) にわたって回転させながら、点 \(A, C\) を \(\text{top4}(\overrightarrow{v}), \text{top4}(-\overrightarrow{v})\) の中から選んで \(\overrightarrow{AC}\) の候補を列挙する。
- \(\overrightarrow{AC}\) の候補は \(O(N)\) 個である。
- \(\overrightarrow{AC}\) の候補を偏角ソートする。
- ベクトル \(\overrightarrow{AC}\) の候補を走査し、\(v := \text{rot}(\overrightarrow{AC})\) とする。点 \(B, D\) を \(\text{top4}(\overrightarrow{v}), \text{top4}(-\overrightarrow{v})\) の中から選んで、面積 \(|\overrightarrow{AC} \times \overrightarrow{BD}|\) を計算する。
このアルゴリズムは、「目標ベクトル \(\overrightarrow{v}\) を \(360^\circ\) にわたって回転させながら \(\text{top4}(\overrightarrow{v})\) を計算する」のにかかる計算量を \(f(N)\) として、\(f(N) + O(N \log N)\) 時間で動作します。
9. \(\text{top4}(\overrightarrow{v})\) の列挙
\(\overrightarrow{v}\) を回転させながら \(\text{top4}(\overrightarrow{v})\) を列挙するための方法として、比較的実装しやすいと思われる \(O(N (\log N)^2)\) 時間の方法を紹介します。
セグメント木状のデータ構造を作成し、区間 \([l, r)\) に対応するノードでは以下を管理します。
top4: 色が \([l, r)\) である点集合に対する \(\text{top4}(\overrightarrow{v})\)v_next: \(\overrightarrow{v}\) を回転させたとき、次にこのノードの \(\text{top4}(\overrightarrow{v})\)、または子孫のいずれかの \(\text{top4}(\overrightarrow{v})\) が更新されるのはいつか？
セグメント木のモノイドは以下のように実装できます。
top4: 子の top4 を集めた \(8\) 頂点から \(4\) 頂点を選ぶv_next: \(8\) 頂点から選ぶ top4 が変化するタイミングと、左右の子のv_nextの中から最も早いものを選ぶ
\(\overrightarrow{v}\) を回す際には、\(\overrightarrow{v}\) を根のノードの v_next に更新し、 v_next がこれと一致するノードすべてを下から再計算すれば良いです。
\(\overrightarrow{v}\) を一周させるときのノード \([l, r)\) の top4 の更新回数は、色が \([l, r)\) である頂点の個数を \(n\) として \(O(n)\) であるので、\(O(N (\log N)^2)\) 時間で \(\text{top4}(\overrightarrow{v})\) を列挙することができます。
投稿日時:
最終更新: