E - ペアの選定 / Choosing Pairs 解説 by admin
Claude Opus 5 (High)概要
\(N\) 人の中から \(2\) 人を選ぶ組 \((i,j)\) のうち、\(A_i+A_j \ge X\) かつ \(B_i+B_j \ge Y\) を満たすものの個数を数える問題です。\(N \le 10^5\) なので全ペア列挙（\(O(N^2)\)）では間に合わず、ソート＋二分探索＋BIT（フェニック木） で \(O(N\log N)\) に落とします。
考察
素朴な方法
すべての組 \((i,j)\) を二重ループで調べると、組の個数は約 \(\frac{N^2}{2} = 5\times 10^9\) 個になり、確実に TLE します。
条件を「片方を固定した数え上げ」に変形する
部員 \(i\) を固定すると、条件は
- \(A_j \ge X - A_i\)
- \(B_j \ge Y - B_i\)
という「\(j\) に関する 2 つの下限条件」になります。つまり平面上の点 \((A_j,B_j)\) のうち、右上の四分領域に入る点の個数を数える問題（2 次元 dominance counting）です。
条件が 1 つだけ（例えば \(A\) のみ）なら、\(A\) をソートして二分探索するだけで数えられます。しかし条件が 2 つあると、単純なソートだけでは「\(A\) の条件を満たす集合の中で \(B\) の条件も満たす個数」が分からないため、工夫が必要です。
解決の方針：片方をソート順で処理、もう片方を BIT で管理
点を \(A\) の昇順にソートしておきます。すると \(i\) を \(A\) の小さい順に見ていったとき、
\[\text{閾値 } thr = X - A_i\]
は単調に減少します。したがって「\(A_j \ge thr\) を満たす \(j\) の集合」は、ソート後の配列の末尾からの連続区間（接尾辞）であり、\(i\) が進むにつれてこの区間は広がるだけです（縮まない）。
そこで、尺取り法（two pointer）で「\(A\) の条件を満たす点」を順次 BIT に追加していき、追加済みの点の中から \(B_j \ge Y - B_i\) となるものの個数を BIT で数えれば、各 \(i\) について \(O(\log N)\) で答えが求まります。
重複と自分自身の処理
この数え方では、\((i,j)\) と \((j,i)\) の両方（順序付きペア）が数えられます。また、\(j=i\) 自身も条件を満たす場合（\(2A_i \ge X\) かつ \(2B_i \ge Y\)）にカウントされてしまいます。よって
\[\text{答え} = \frac{(\text{数えた総数}) - (\text{自分自身が条件を満たす人数})}{2}\]
とすればよいです。条件が \(i,j\) について対称なので、この式が成り立ちます。
アルゴリズム
- 点 \((A_i,B_i)\) を \(A\) の昇順にソートし、配列
A,Bを作る。 Bの値を座標圧縮する（値が \(10^9\) まであるので BIT の添字にできない）。us=Bのソート済み重複除去列、rank[i]=B[i]の順位（1-indexed）。- BIT（サイズ \(m=|us|\)、各位置の個数を管理）を用意し、ポインタ
p = n（挿入済みはp以降）とする。 - \(i = 0,1,\dots,N-1\) の順に：
thr = X - A[i]として、A[p-1] >= thrの間pを減らし、その点のrankを BIT に \(+1\) 挿入する。t = Y - B[i]として、idx = bisect_left(us, t)（= \(B < t\) の値の個数）を求め、BIT で「\(B < t\) の挿入済み点数」sを求める。- 挿入済み総数は
n - pなので、条件を満たす個数は(n - p) - s。これをtotalに足す。
- \(2A_i \ge X\) かつ \(2B_i \ge Y\) となる \(i\) の個数
self_を数える。 (total - self_) // 2を出力する。
具体例
\(N=3, X=5, Y=5\)、点が \((1,4),(3,3),(4,2)\)（すでに \(A\) 昇順）のとき：
- \(i=0\)：\(thr=4\) → \((4,2)\) を挿入。\(t=5-4=1\) → \(B\ge1\) は 1 個。
total=1 - \(i=1\)：\(thr=2\) → \((3,3)\) を挿入（挿入済み \(\{2,3\}\)）。\(t=2\) → 2 個。
total=3 - \(i=2\)：\(thr=1\) → \((1,4)\) を挿入（挿入済み \(\{2,3,4\}\)）。\(t=3\) → \(B\ge3\) は 2 個。
total=5 - 自分自身：\((3,3)\) のみ（\(6\ge5, 6\ge5\)）→
self_=1 - 答え：\((5-1)/2 = 2\)
実際、条件を満たすのは \(\{(1,4),(4,2)\}\)（和 \(5,6\)）と \(\{(3,3),(4,2)\}\)（和 \(7,5\)）の 2 組で一致します。
計算量
- 時間計算量: \(O(N \log N)\)（ソート、座標圧縮の二分探索、BIT の各操作が \(O(\log N)\)、
pの移動は全体で \(N\) 回） - 空間計算量: \(O(N)\)
実装のポイント
ポインタ
pは巻き戻さない：Aを昇順ソートしたことで閾値が単調減少するため、pは単調に減るだけです。これにより挿入回数は合計 \(N\) 回で済みます。もし逆順にソートしてしまうと単調性が崩れるので注意。座標圧縮：\(B_i \le 10^9\) なので BIT の添字に直接使えません。
sorted(set(B))で圧縮し、bisect_leftで順位を得ます。「\(B \ge t\)」の数え方：BIT は「先頭からの累積和」が得意なので、まず
idx = bisect_left(us, t)（= 圧縮後で \(B<t\) となる位置数）を求め、BIT の \([1,\,idx]\) の和s= 「\(B<t\) の挿入済み個数」を計算し、(挿入済み総数) - sとします。\(t \le 0\) でもidx = 0になり正しく全件が数えられます。順序付き→無序への変換：最後に自己ペアを引いて 2 で割るのを忘れないこと。\(X,Y\) は最大 \(2\times10^9\) で \(2A_i\) も同様に大きいので、C++ 等では 64bit 整数を使う必要があります（答えも最大約 \(5\times10^9\)）。
高速入力：\(N=10^5\) 行の入力なので、Python では
sys.stdin.buffer.read().split()で一括読み込みすると安全です。BIT も関数呼び出しを避けてループを直書きすると高速です。ソースコード
import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); X = int(data[1]); Y = int(data[2])
pts = sorted((int(data[3 + 2 * i]), int(data[4 + 2 * i])) for i in range(n))
A = [p[0] for p in pts]
B = [p[1] for p in pts]
us = sorted(set(B))
m = len(us)
rank = [bisect_left(us, b) + 1 for b in B]
tree = [0] * (m + 1)
p = n
total = 0
for i in range(n):
thr = X - A[i]
while p > 0 and A[p - 1] >= thr:
p -= 1
k = rank[p]
while k <= m:
tree[k] += 1
k += k & -k
t = Y - B[i]
idx = bisect_left(us, t)
s = 0
k = idx
while k > 0:
s += tree[k]
k -= k & -k
total += (n - p) - s
self_ = 0
for i in range(n):
if 2 * A[i] >= X and 2 * B[i] >= Y:
self_ += 1
sys.stdout.write(str((total - self_) // 2) + "\n")
main()
この解説は claude5opus-high によって生成されました。