Coder-Strike 2014 Final - C. Bug in Code

１ミスしたけどこれはすんなり方針が立った。
http://codeforces.com/contest/420/problem/C

問題

N人の人がいて、その中に犯人がいる。
各人、自分以外で犯人だと思う人を２人心に思い描いている。

N人の中から２人選んだ時、N人中P人がその２人に犯人が含まれていると賛成するように選びたい。
そのような２人組の組み合わせ数を答えよ。

解法

i番を犯人だと思う人がx人いる場合、残り(N-x)人のうち(P-x)人以上がj番を犯人だと思ってるなら、(i,j)のペアは題意を満たす。

まずN人の考えをたどり、各人何人に疑われているかをカウントする。
以後、i番目の人を一人目に選んだ場合に、i番をx人が犯人だと思うなら、(i+1)～N番目のうち(P-x)人以上から犯人と思われてる人の数を数えればいい。

これにはBITを使って処理できる。
BITを使って、(P-x)人以上から疑われている人をO(logN)で数え上げることができる。

各iについて以下のように処理すればよい。

1. j>iとなる各jについて、iを犯人と思ってる人がいればその人はもう一人がだれだろうと賛成者になるので、その分j番の疑われている数を減らし、BITを更新する。
2. i番を疑う人がx人いるなら、BITから(P-x)人以上から疑われている人の数を求める。
3. 1番の処理で減らしたj番の疑われている人数をもとに戻す。
4. i番をBIT上に登録する

BITの更新回数は全部でN回なので、全体の処理はO(N*logN)。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	BIT(){clear();};
	void clear() {ZERO(bit);};
	
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};
BIT<int,20> bt;


int N,P;
vector<int> E[300001];
int inin[300001];
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>P;
	FOR(i,N) {
		cin>>x>>y;
		x--,y--;
		if(x>y) swap(x,y);
		E[x].push_back(y);
		inin[x]++;
		inin[y]++;
	}
	
	ll tot=0;
	for(i=N-1;i>=0;i--) {
		sort(E[i].begin(),E[i].end());
		FOR(j,E[i].size()) {
			bt.update(inin[E[i][j]]+1,-1);
			inin[E[i][j]]--;
			bt.update(inin[E[i][j]]+1,1);
		}
		
		if(inin[i]>=P) tot+=N-1-i;
		else tot+=N-1-i-bt.total(P-inin[i]);
		
		FOR(j,E[i].size()) {
			bt.update(inin[E[i][j]]+1,-1);
			inin[E[i][j]]++;
			bt.update(inin[E[i][j]]+1,1);
		}
		
		bt.update(inin[i]+1,1);
	}
	cout << tot << endl;
}

まとめ

他の人はほかの手段で解いてる人が多かった気がする。