kmjp's blog

競技プログラミング参加記です

ゆるふわ競プロオンサイト #2 : L - rival

これ色んな解法ありそう。
https://www.hackerrank.com/contests/yfkpo2/challenges/rival

問題

N体のゴリラがいる。
各ゴリラの体力はP[i]であり、自身がライバルとみなす体力の範囲は[L[i],R[i]]である(L[i]≦P[i]≦R[i])。
互いにライバルとみなすようなゴリラの対は何通りか。

解法

同じ体力のゴリラ同士は必ずライバル関係にあるので、まずそれらをカウントする。
Pの取りえる値の範囲が狭いので、これを総当たりしよう。

体力がxであるようなゴリラiのL[i]の集合をL'(x)、R[i]の集合をR'(x)と置くことにする。
L'(x)とR'(x)は先にソートしておく。

さて、体力がxであるゴリラとyであるゴリラが互いに何体かいたとき、条件を満たすのは何通りか考える。
x<yとすると、R'(x)のうちy以上の数と、L'(y)のうちx以下の数の積を取ればよい。
これはそれぞれlower_boundで数え上げることができる。

int N;
vector<int> R[1010];
vector<int> L[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>x>>j>>k;
		ret+=L[x].size();
		L[x].push_back(j);
		R[x].push_back(k);
	}
	FOR(i,1001) {
		sort(ALL(L[i]));
		sort(ALL(R[i]));
	}
	FOR(y,1001) FOR(x,y) {
		int mor=R[x].size()-(lower_bound(ALL(R[x]),y)-R[x].begin());
		int le=lower_bound(ALL(L[y]),x+1)-L[y].begin();
		ret+=1LL*le*mor;
	}
	cout<<ret<<endl;
	
}

まとめ

これ想定解なんなんだろうな。