ARC084 C : Snuke Festival(300)
作成日：2017.11.05
最終更新日：2017.11.05
問題概要
上部、中部、下部の3つのパーツからなる祭壇を作る。
各部位のパーツはそれぞれ$N$個ずつあり、大きさは順に$A_i$,$B_i$,$C_i$である。
祭壇は$A_x$$< B_y$$< C_z$となるパーツを組み合わせることでのみ作ることができる。
この時、作ることができる祭壇は何種類あるか求めよ。
制約
$1 \leq N \leq 10^5$
$1 \leq A_i , B_i , C_i \leq 10^9$
入力はすべて整数
考え方
$A$と$B$の2つのパーツだけがある場合を考える。
この時$A_i$を決めると条件を満たす$B_j$の個数は$O(N)$で求められる。
このままだと全体で$O(N^2)$となり間に合わないが、$A$,$B$をともにソートするとポインタを一方向にのみ進めれば良くなることから$O(N)$で求められるようになる。
元の問題に戻ると、$B$を固定するごとに条件を満たす$A$及び$C$の個数を求めてその積の総和を求めれば良い。
これは先に考えたものと同様にすることで$O(N)$で求めることができる。
ソースコード
マクロ等はこちら
const int MC = 100010;
int N;
int A[MC],B[MC],C[MC];
LL ansB[MC];
LL ans;
int main(){
cin >> N;
repp(i,0,N) cin >> A[i];
repp(i,0,N) cin >> B[i];
repp(i,0,N) cin >> C[i];
A[N] = B[N] = C[N] = 1e9 + 7;
sort(A,A+N);
sort(B,B+N);
sort(C,C+N);
int x = 0 , z = 0;
repp(i,0,N){
while(A[x] < B[i]) ++x;
while(C[z] <= B[i]) ++z;
ans += (LL)x * (N-z);
}
cout << ans << endl;
return 0;
}解法まとめ
$A$,$B$,$C$をソートし、$B$を固定するごとに条件を満たす$A$の個数と$C$の個数の積を求めて答えに加算する。(13-21行)