Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-06-24

[][] TopCoder TCO Round 2C Level2 (500) ThreePoints 20:09 はてなブックマーク -  TopCoder TCO Round 2C Level2 (500) ThreePoints - 練習帳

問題文

 問題文

概要

  • 2次元平面上にn点が与えられている。
    • どの2点をとってもx座標は等しくない。また、どの2点をとってもy座標は等しくない。
  • 次の条件を満たす3点の組(A, B, C)の個数を答えよ:条件「A[x] < B[x] < C[x]かつA[y] < C[y] < B[y]、ここでP[x], P[y]はそれぞれ点Pのx, y座標を表す」
  • 制限:n ≦ 300000, 点のx, y座標は0以上10**9未満の整数値

コード

 Practiceでの提出コード(gist):https://gist.github.com/2863529

 (SRM終了直後の感想戦とPracticeで解答例を見た後に作成しています)

考えた過程

方針

点vについて,vより右上にある点をR[v],左下にある点をL[v]とすると,答えはΣ_{v} R[v]*(R[v]-1)/2 - R[v]*L[v]となります.具体的には,x座標について点をソートし,(x座標が小さい点はy座標が何番目に小さいか)を計算します(上の提出コードではperm[i]で書いています).これの数え上げにはBITを用いています,

どうやって思いつこう

それぞれの点を上の条件の点Aに対応させ,各点Aに対してB, Cの組が何個あるかを考えます・・・(*).B, Cは両方とも必ず右上になければなりません.ただ,B, Cがすべての右上に全部が条件を満たす訳ではありません.なので(1)の問題の前に,B, Cの配置でどのようなものが条件を満たすかを考えてみます.そのために,まず2つの点の配置関係を考えてみます.すると,x, y座標が一致する点がないという条件があるので,/(一方が右上にある)という関係と\(右下にある)の関係しかない事が分かります.

うまく問題の条件を使って問題を簡単に出来たので,この方針は悪くなさそうです.

ナイーブな方法では数え上げられない

では,(*)の問題,すなわち,各Aに対して,B, Cが/の関係になっている組の数は何個あるかを計算します.これにはAより右上にあるそれぞれの点Bに対して,Bより右上にある点が何個あるかを求め,それをすべて足さなければなりません.すなわたい2重ループです.点が300000個あるので,n**2の計算はできません.これをどう解消するかがこの問題のポイントなのだと思います.それぞれの点について「自分より右上にある点の数」を保存しておく事は出来ます,これは後で使うかもしれないので念頭に置いておきます.

真ん中の点を用いて数え上げる

/の関係になっている3つ組全体の個数を数え上げるときにΣを2回計算しなければならないのは,左下の点について分類している為です。これを真ん中の点を用いて分類すると,前述のように(左上の点)*(右下の点)で数え上げられてしまいます.これは1重ループで計算できてしまいます.多分この部分に発想の飛躍がある所なのだと思います.後はそれぞれの点について右上にある点の個数だけではなく,左下にある点の個数も予めBITなどで計算しておけば、答えが得られます.