Editorial - AtCoder Weekday Contest 0195 Beta

Official

E - ペアの選定 / Choosing Pairs Editorial by admin

Claude Opus 5 (High)

概要

$N$ 人の中から $2$ 人を選ぶ組 $(i,j)$ のうち、$A_i+A_j \ge X$ かつ $B_i+B_j \ge Y$ を満たすものの個数を数える問題です。「$2$ つの条件を同時に満たすペアを数える」典型問題で、片方をソート＋尺取り法、もう片方を BIT（フェニック木）で処理します。

考察

素朴なアプローチ

すべての組 $(i,j)$ を全探索すると $O(N^2)$ で、$N = 10^5$ のとき約 $5 \times 10^9$ 回の判定が必要になり TLE します。

気づき 1：順序付きペアで数えると扱いやすい

「$i < j$」という制約があると片側だけを見る必要があり扱いにくいので、いったん 順序付きペア $(i,j)$（$i \ne j$）で条件を満たす個数を数えます。条件 $A_i+A_j\ge X$、$B_i+B_j\ge Y$ は $i,j$ について対称なので、$(i,j)$ が条件を満たすなら $(j,i)$ も満たします。よって

\[(\text{答え}) = \frac{(\text{順序付きペアの個数})}{2}\]

となります。実装上は「$j$ が $i$ 自身でもよい」として数えたあとに $i=j$ の場合（$2A_i \ge X$ かつ $2B_i \ge Y$ となる $i$）を引くのが楽です。

気づき 2：$A$ でソートすると条件 1 は「接尾辞」になる

$A$ の昇順に並べ替えておきます（以下、並べ替え後の配列を $a, b$ とします）。このとき、固定した $i$ に対して条件 $a_i + a_j \ge X$、すなわち $a_j \ge X - a_i$ を満たす $j$ の集合は、ソート済みなので 配列の後ろ側の連続区間（接尾辞） $[p_i, N)$ になります。

さらに $i$ を小さい方から動かすと $a_i$ は単調増加するので、しきい値 $X - a_i$ は単調減少し、境界 $p_i$ は単調に左へ動きます。したがって 尺取り法（two pointer） で $p$ を全体 $O(N)$ で管理できます。

気づき 3：条件 2 は「区間内で $b_j \ge$ しきい値」の個数

残るのは「接尾辞 $[p,N)$ の中で $b_j \ge Y - b_i$ を満たす $j$ の個数」です。接尾辞は $i$ が進むにつれて要素が追加されるだけ（削除されない）なので、追加のたびに $b_j$ を BIT に登録しておけば、「登録済みの中で値が $Y-b_i$ 以上のものの個数」をクエリすればよいことになります。

$b$ の値は最大 $10^9$ なので、座標圧縮して BIT のサイズを $O(N)$ に抑えます。

アルゴリズム

$(A_i, B_i)$ を $A$ の昇順にソートし、$a, b$ とする。
$b$ の値を座標圧縮し、サイズ $M \le N$ の BIT を用意する（各値の出現個数を管理）。
ポインタ $p = N$、カウンタ $total = 0$、$selfCount = 0$ とする。
$i = 0, 1, \dots, N-1$ の順に：
- $a_{p-1} \ge X - a_i$ である間 $p$ を $1$ 減らし、その $b_p$ を BIT に登録する（登録数 $inBit$ も更新）。これで BIT には「条件 1 を満たす $j$ の $b$ 値」がすべて入っている。
- $need = Y - b_i$ とし、圧縮座標で $need$ 以上の最初の位置 $pos$ を二分探索で求め、 $$cnt = inBit - (\text{BIT の } [0,pos) \text{ の総和})$$ すなわち「$b_j \ge need$ の個数」を得て $total$ に足す。
- $i$ 自身も接尾辞に含まれ（$i \ge p$）、かつ $2b_i \ge Y$ なら、$j=i$ が誤って数えられているので $selfCount$ を $1$ 増やす。
答えは $(total - selfCount)/2$。

具体例：$N=3$, $X=5$, $Y=5$, $(A,B) = (1,4),(3,3),(4,1)$ の場合。$A$ 昇順のまま。 - $i=0$（$a=1$）：$a_j \ge 4$ が必要 → $j=2$ のみが BIT に入る。$b_j \ge 1$ の個数 $= 1$。 - $i=1$（$a=3$）：$a_j \ge 2$ → $j=1,2$ が入る。$b_j \ge 2$ の個数 $=1$（$b_1=3$）。$i=1$ 自身は $2b_1=6\ge5$ なので self に該当 → $selfCount=1$。 - $i=2$（$a=4$）：$a_j\ge1$ → 全員。$b_j\ge4$ の個数 $=1$（$b_0=4$）。 $total = 3$, $selfCount = 1$ より答えは $(3-1)/2 = 1$（実際に $(1,2)$ 番目の $(1,4),(3,3)$ が条件を満たす）。

計算量

時間計算量: $O(N \log N)$（ソート、座標圧縮の二分探索、BIT の各操作が $O(\log N)$、ポインタ移動は全体で $O(N)$）
空間計算量: $O(N)$

実装のポイント

オーバーフローに注意：$X, Y \le 2\times10^9$ は 32bit 整数に収まらないので long long（Python なら気にしなくてよいが C++ では必須）で受け取ります。$X - a_i$ や $Y - b_i$ の計算も 64bit で行います。答えも最大約 $5\times 10^9$ になるため long long が必要です。
BIT で「しきい値以上の個数」を求める：BIT は接頭辞和が得意なので、(登録総数) - (しきい値未満の個数) として求めます。lower_bound で得た位置 $pos$ が「$need$ 未満の要素数」に対応する点を利用します。
$j = i$ の除外を忘れない：条件 1 を満たす接尾辞に $i$ 自身が入りうる（$2a_i \ge X$ のとき）ので、$2b_i \ge Y$ も成り立つケースを引かないと答えがずれます。
同じ値の扱い：$A$ に等しい値が複数あっても、尺取りの条件を a[p-1] >= X - a[i] と非等号込みで書けば正しく接尾辞が取れます（順序付きで数えて最後に $2$ で割る方式なので、ソートの安定性やタイブレークは結果に影響しません）。
平方分割やマージソート（BIT を使わない転倒数風の数え方）でも同様に実装できますが、BIT が最も簡潔です。

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<int> t;
    BIT(int n_=0):n(n_),t(n_+1,0){}
    void add(int i,int v){ for(++i;i<=n;i+=i&-i) t[i]+=v; }
    int sum(int i){ int s=0; for(;i>0;i-=i&-i) s+=t[i]; return s; } // prefix [0,i)
};

int main(){
    int N; long long X, Y;
    scanf("%d %lld %lld", &N, &X, &Y);
    vector<long long> A(N), B(N);
    for(int i=0;i<N;i++){
        long long a,b; scanf("%lld %lld",&a,&b);
        A[i]=a; B[i]=b;
    }
    vector<int> idx(N);
    for(int i=0;i<N;i++) idx[i]=i;
    sort(idx.begin(), idx.end(), [&](int x,int y){ return A[x]<A[y]; });
    vector<long long> a(N), b(N);
    for(int i=0;i<N;i++){ a[i]=A[idx[i]]; b[i]=B[idx[i]]; }

    vector<long long> comp = b;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int M = comp.size();
    BIT bit(M);

    auto compIdx=[&](long long v)->int{
        return (int)(lower_bound(comp.begin(), comp.end(), v) - comp.begin());
    };

    long long total = 0;
    long long selfCount = 0;
    int p = N;
    int inBit = 0;
    for(int i=0;i<N;i++){
        while(p>0 && a[p-1] >= X - a[i]){
            p--;
            bit.add(compIdx(b[p]), 1);
            inBit++;
        }
        // count j in [p,N) with b[j] >= Y - b[i]
        long long need = Y - b[i];
        int pos = compIdx(need); // first index with comp >= need
        long long cnt = (long long)inBit - bit.sum(pos);
        total += cnt;
        if(i >= p && 2*b[i] >= Y) selfCount++;
    }
    long long ans = (total - selfCount)/2;
    printf("%lld\n", ans);
    return 0;
}

この解説は claude5opus-high によって生成されました。

E - ペアの選定 / Choosing Pairs Editorial by admin

概要

考察

素朴なアプローチ

気づき 1：順序付きペアで数えると扱いやすい

気づき 2：\(A\) でソートすると条件 1 は「接尾辞」になる

気づき 3：条件 2 は「区間内で \(b_j \ge\) しきい値」の個数

アルゴリズム

計算量

実装のポイント

ソースコード