geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC248 参加記録

ABC 計算幾何直線ウェーブレット行列

コンテスト中AC:A〜D

D - Range Count Query
E - K-colinear Line

D - Range Count Query

ウェーブレット行列が使えます。
ウェーブレット行列には以下の関数があります。

計算量は、今回の場合 $A$ の要素の最大値 $A_{max}$ をとって、 $O(logA_{max})$ です。

各クエリは、 $quantile(L,R+1,X,X+1)$ とすることで答えられます。
よって、すべてのクエリを $O(QlogA_{max})$ で計算できます。

ウェーブレット行列の構築に $O(NlogA_{max})$ かかるので、全体で $O((N+Q)logA_{max})$ です。
提出コード

E - K-colinear Line

$K=1$ の時は無限に存在するので、"Infinity"です。

そうでない時、2点を決めれば直線を一意に定められるので2点を全探索します。

悩んだのが、同じ直線を2回以上使わないようにする処理です。

色々調べたことを書いておきます。

まず、2点 $(x_i,y_i),(x_j,y_j)$ を通る直線の式はググりました。

二点を通る直線の方程式の３タイプ | 高校数学の美しい物語

$y-y_i = \frac{y_j - y_i}{x_j - x_i}(x-x_i)$

$ax+by+c=0$ の $(a,b,c)$ で管理

式変形すると、

$-(y_j - y_i)x+(x_j - x_i)y + y_i(x_j - y_i) - x_1(y_j - y_i)=0$

なので、

$a = -(y_j - y_i)$
$b = x_j - x_i$
$c = y_i(x_j - x_i) - x_i(y_j - y_i)$

であり、これを管理します。

↓のtwitterで言及されていましたが、一意性を保つために正規化する必要があります。

熨斗袋 on Twitter: "格子点を通る直線は ax + by = c の形式で管理するのが楽なんじゃないかなと思う。"

熨斗袋 on Twitter: "gcd で割ったあと、min {(a, b, c), (-a, -b, -c)} で正規化"

$gcd(a,b,c)=1$ にする
以下の2つは同じ式です。
$x+2y-3=0$
$2x+4y-6=0$
これを同一視するため、 $g=gcd(a,b,c)$ として、 $g$ で $a,b,c$ を割ります。
符号を揃える
以下の2つは同じ式です。
$x+2y-3=0$
$-x-2y+3=0$
これを同一視するため、(表現が正しいかわかりませんが、)符号を揃えます。
先程のツイートで言うところの、min({a,b,c}, {-a,-b,-c})を採用するのと同じだと思います。

下記実装では、構造体を作ってみました。
提出コード

$y=\frac{d}{e}x+\frac{f}{g}$ の $(d,e,f,g)$ で管理

$d = y_j - y_i$
$e = g = x_j - x_i$
$f =y_1(x_j - x_i) - x_1(y_j-y_i)$

となります。小数での管理は誤差が心配なので、分数で管理します。

分数 $\frac{p}{q}$ でも気をつける点があります。

$gcd(p,q)=1$ にする。すなわち、 $gcd(p,q)$ で $p,q$ を割る
符号を揃える。(正,正)なら(負,負)に、(正,負)にする。(これもmin({p,q},{-p,-q})で良さそうです)

また、この実装では、 $e=g=0$ のパターン、すなわち、y軸に平行な直線の場合は例外処理が必要です。
$x = x_i$ として、y軸に平行な直線の $x$ 座標を別に管理しておけば良いです。

これも構造体を作ってみました。

提出コード

あと、公式解説と他の方の実装についても書いておきます。

探索済みの点対を管理

公式解説の方法です。

点 $P_i = (X_i , Y_i)$ とします。

flag[i][j]を点iと点jが探索済みならtrue、そうでなければfalseとします。
初め、全てfalseにします。

ある同一直線上にある全ての点の集合を、 $S$ とします。 $S$ に含まれるすべての点対 $(P_i,P_j)$ に対して、
flag[i][j] = true
とします。
こうすることで、全探索の際にflag[i][j]=falseである点対だけ直線を求めればよいことになります。

基準となる2点を管理

他の方の実装を参考にした時によく見られました。

直線は2点によって一意に定めることができるので、先程の集合 $S$ を何らかの基準でソートして、小さい方の2点を記録すること等で管理可能です。

点が直線上にあるかの判定

直線上であるかどうかの判定は、直線 $ax+by+c=0$ の式に代入していましたが、外積でいけるようです。