E - ペアの選定 / Choosing Pairs Editorial by admin
gpt-6-astra-medium概要
技術力の合計が \(X\) 以上、かつ体力の合計が \(Y\) 以上になる部員のペアを数えます。技術力でソートして候補を管理し、体力の条件を満たす人数を Fenwick Tree（BIT）で高速に求めます。
考察
1. 全ペアの確認では間に合わない
すべての組 \((i,j)\) を調べる方法では、時間計算量が \(O(N^2)\) になります。
\(N=10^5\) のとき、調べるペアは約 \(50\) 億組になるため、この方法では実行時間に間に合いません。
2. 技術力でソートすると、候補を追加するだけでよい
ある部員の技術力・体力を \((a,b)\) とすると、相手に必要な条件は次のとおりです。
- 技術力が \(X-a\) 以上
- 体力が \(Y-b\) 以上
ここで、部員を技術力の昇順にソートし、その順番で注目する部員を変えていきます。
注目する部員の技術力 \(a\) は減らないため、相手に必要な技術力 \(X-a\) は増えません。したがって、技術力の条件を満たす候補は増えるだけで、取り除く必要がありません。
例えば \(X=10\) の場合、注目する部員の技術力が \(3,5,7\) と増えると、相手に必要な技術力は \(7,5,3\) と下がります。
そこで、ソートした配列の末尾からポインタを動かし、技術力の条件を満たす部員を順にデータ構造へ追加します。
3. 体力の条件は Fenwick Tree で数える
技術力の条件を満たす候補の中から、さらに体力が \(Y-b\) 以上の人数を求めたいです。
これは、次の引き算で求められます。
\( \text{条件を満たす人数}=\text{候補の総人数}-\text{体力が }Y-b\text{ 未満の候補の人数} \)
Fenwick Tree は、各位置への個数の追加と、先頭からある位置までの個数の合計を、それぞれ \(O(\log N)\) で処理できます。
ただし、体力は最大 \(10^9\) なので、その値をそのまま配列の添字にはできません。体力の値を小さい順の番号に置き換える座標圧縮を行い、Fenwick Tree で管理します。
4. 自分自身と重複を補正する
この方法では、相手の候補を「自分より後ろの部員」に限定しません。そのため、次の補正が必要です。
- 自分自身も条件を満たすなら、その \(1\) 人分を引く。
- 異なる部員のペアは両方向から数えているので、最後に \(2\) で割る。
自分自身が数えられるのは、\(2a\ge X\) かつ \(2b\ge Y\) の場合です。
アルゴリズム
以降の添字は、技術力の昇順にソートした後の \(0\) 始まりの添字とします。並べ替えても、部員同士のペアとその条件は変わりません。
部員を技術力の昇順にソートする。
体力を座標圧縮する。
- 全部員の体力を集め、ソートして重複を取り除いた配列
coordinatesを作ります。 - 各部員の体力がこの配列の何番目にあるかを
b_indexに保存します。
- 全部員の体力を集め、ソートして重複を取り除いた配列
候補を管理する変数を初期化する。
pointer = N - 1：次に候補へ追加する部員の位置active = 0：追加済みの候補の人数answer = 0：条件を満たす相手の人数の累計- Fenwick Tree：追加済みの候補を、圧縮後の体力ごとに数える
部員を先頭から順に処理する。
注目する部員の技術力・体力を \((a,b)\) とします。
① 技術力の条件を満たす候補を追加する
pointer が指す部員について、\(A_{\text{pointer}}+a\ge X\) である間、次の処理を繰り返します。
- その部員の体力に対応する位置へ、Fenwick Tree で \(1\) を加算する。
activeを \(1\) 増やす。pointerを \(1\) 減らす。
ソート済みなので、この処理の終了時には、技術力の条件を満たす部員がちょうどすべて登録されています。
② 体力の条件も満たす人数を加算する
lower_bound を使い、coordinates の中で初めて \(Y-b\) 以上になる位置を below とします。
すると、圧縮後の添字が below 未満の値は、ちょうど体力が \(Y-b\) 未満の値です。したがって、
active - fenwick.prefix_sum(below)
を answer に加算します。
例えば、coordinates が \([2,5,8]\)、必要な体力が \(6\) なら、below は \(2\) です。体力 \(2,5\) の候補の人数を候補全体から引けば、体力 \(6\) 以上の候補の人数が得られます。
③ 自分自身を除外する
\(2a\ge X\) かつ \(2b\ge Y\) なら、自分自身が先ほどの人数に含まれるため、answer から \(1\) を引きます。
answer / 2を出力する。
条件を満たす異なる部員のペアは、一方に注目したときと他方に注目したときの合計 \(2\) 回数えられています。そのため、\(2\) で割ると求めるペア数になります。
計算量
- 時間計算量: \(O(N\log N)\)
- 空間計算量: \(O(N)\)
ソートと座標圧縮に \(O(N\log N)\) かかります。pointer は減るだけなので、while 文による追加は全体で高々 \(N\) 回です。各追加と各部員に対する検索・集計は \(O(\log N)\) で処理できます。
実装のポイント
答えには 64 bit 整数を使う
ペア数は最大で \(\frac{N(N-1)}{2}\) となり、32 bit 整数の範囲を超えます。また、最後に \(2\) で割る前の累計も大きくなるため、answerはlong longにします。Fenwick Tree の区間の定義に注意する
このコードのprefix_sum(count)は、圧縮後の添字が \(0\) 以上count未満の範囲の合計を返します。したがって、prefix_sum(below)は体力が \(Y-b\) 未満の人数になります。境界値を含めるために
lower_boundを使う
必要なのは体力が \(Y-b\) 以上の人数です。ちょうど \(Y-b\) の部員を除外しないようにします。技術力についても比較は>=です。同じ体力の部員も、それぞれ \(1\) 人として追加する
座標圧縮では同じ値を同じ位置にまとめますが、Fenwick Tree には部員ごとに \(1\) を加算するため、人数は正しく数えられます。自分自身の除外は、両方の条件を満たす場合だけ行う
技術力だけ、または体力だけの条件を満たす場合には、もともと集計されていないので引いてはいけません。ソースコード
#include <bits/stdc++.h>
using namespace std;
class FenwickTree {
int n;
vector<int> bit;
public:
explicit FenwickTree(int n) : n(n), bit(n + 1, 0) {}
void add(int index) {
for (++index; index <= n; index += index & -index) {
++bit[index];
}
}
int prefix_sum(int count) const {
int result = 0;
for (; count > 0; count -= count & -count) {
result += bit[count];
}
return result;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
long long X, Y;
cin >> N >> X >> Y;
vector<pair<long long, long long>> members(N);
vector<long long> coordinates;
coordinates.reserve(N);
for (auto& [a, b] : members) {
cin >> a >> b;
coordinates.push_back(b);
}
sort(members.begin(), members.end());
sort(coordinates.begin(), coordinates.end());
coordinates.erase(unique(coordinates.begin(), coordinates.end()),
coordinates.end());
vector<int> b_index(N);
for (int i = 0; i < N; ++i) {
b_index[i] = lower_bound(coordinates.begin(), coordinates.end(),
members[i].second) - coordinates.begin();
}
FenwickTree fenwick(static_cast<int>(coordinates.size()));
int pointer = N - 1;
int active = 0;
long long answer = 0;
for (int i = 0; i < N; ++i) {
const auto [a, b] = members[i];
while (pointer >= 0 && members[pointer].first + a >= X) {
fenwick.add(b_index[pointer]);
++active;
--pointer;
}
int below = lower_bound(coordinates.begin(), coordinates.end(), Y - b)
- coordinates.begin();
answer += active - fenwick.prefix_sum(below);
if (2 * a >= X && 2 * b >= Y) {
--answer;
}
}
cout << answer / 2 << '\n';
return 0;
}
この解説は gpt-6-astra-medium によって生成されました。