ABC187-B Gentle Pairs 解説

\(O(N \log N)\) で解きます。

問題

AtCoder Beginner Contest 187 | B - Gentle Pairs

概要

与えられる点の集合 \(S\) の中から二点を選ぶとき、それらを結んだ直線の傾きが \(-1\) 以上 \(1\) 以下になる組み合わせはいくつあるか？

解法

editorial 解は単純にすべてのペアについて調べるだけですが、ここでは他の解き方を紹介します。

まず、こういう図を想像します。

点 \(\mathrm{P}\) と結んだ時に傾きが \(-1\) 以上 \(1\) 以下になるのは灰色で塗られた範囲です。よって、 \((\mathrm{P}, \mathrm{Q})\) は条件を満たしますが、 \((\mathrm{P}, \mathrm{R})\) は満たさないことが見て取れます。

この図を左に \(45^\circ\) 回転してみます。

\(45^\circ\) 回転した座標系を新たに考えると、問題の条件は「自分より左下、または右上にある」と言い替えることができます。

よって、全ての点について自身の左下にいくつの点があるかを数えることで、全てのペアを重複なく数えることができます。 これは、 \(X\) 座標の小さい順に点を見ていき、今見ている点より \(Y\) 座標の小さな点がこれまでにいくつあったかが計算できれば良いので、 平衡二分木やFenwick Treeを使うことで \(O(N \log N)\) で解くことができます。 （「平面走査」と呼ばれるテクニックです。）

実装

今回の制約ではわざわざ座標圧縮を行う必要はありませんが、負数がなくなるよう底上げする処理が必要なのでせっかくだしやることにしました。

提出コード（Python）

class FenwickTree:
    # 実装略

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

# 座標変換
P = [(x-y, x+y) for (x, y) in P]

# 座標圧縮
def compress(p):
    x_set = sorted(set([x for (x, y) in p]))
    y_set = sorted(set([y for (x, y) in p]))
    x_dict = {x:i for i, x in enumerate(x_set)}
    y_dict = {y:i for i, y in enumerate(y_set)}
    return [(x_dict[x], y_dict[y]) for (x, y) in p]

P = compress(P)

# 平面走査
P.sort()
bit = FenwickTree(N)
ans = 0
for (_, y) in P:
    ans += bit.bitsum(y+1)
    bit.bitadd(y, 1)
print(ans)