幾何パートとデータ構造パートに分かれている問題。幾何パートで下手な考察をして、場合分けと実装を爆発させてしまった。
データ構造パートで解説と違うことをしていたので、主にその部分について整理する。
問題
解法
解説にある最初の満点解法の、「aとbを入れ替える」条件を、サイズに依存するようにした解法。
(D1,E1)を点P1、(D2,E2)を点P2とする。また、i番目のドラゴンの位置をp[i]とする。
図を書いて頑張って考えてみる。
すると、各クエリでは、iを種族fの点、jを種族gの点として、(p[i]とP1のなす角,p[i]とP2のなす角)と(p[j]とP1のなす角、p[j]とP2のなす角)がある順序関係を満たすような(i,j)の組の数を数えればよいということが分かる。
これは、それぞれを二次元平面上の点と見て、x座標でソートしてy座標をBITで見れば、O((fのサイズ+gのサイズ)logN)で可能。全てのクエリでこれをすると、計算量はO(QNlogN)で、小課題2が解ける。
ここで、「同じペアはクエリに現れない」「各種族のサイズの合計がNで抑えられる」ということに注目すると、オーダーをmin(fのサイズ,gのサイズ)のみに依存するようにすると計算量が落ちそうという予想が立つ。
毎クエリでf,gの小さい方だけ走査するとき、走査数の合計はどのくらいだろうか。各種族のサイズで場合分けしてみる。
・サイズが√N以上のもの:それを走査するのが必要な相手はO(√N)個で、サイズの合計がO(N)なので、O(N√N)
・サイズが√N未満のもの:毎クエリO(√N)なので合計でO(Q√N)
よって、O((N+Q)√N)回となる。
fとgが非対称に見えるが、図を書いて頑張って考えると、逆にしても実際の処理は同じような問題に帰着できることが分かる。
サイズの大きい側のvectorにpush_backしていき、クエリを読んだ後に全てオフラインで処理すれば、1クエリO(logN)で分かるので、全体でO((N+Q)√NlogN)で解けた。
実装
ラムダ式でまとめたけど場合分けがひどい......。
atcoder.jp
感想
「本番中に通す難易度」は絶対に難易度12だと思う。2017年のめちゃくちゃ強い人たちが誰も小課題2以降を取ってない時点でお察し。
