TopCoder SRM 803 : Div1 Easy Div2 Hard MarriageAndCirclingChallenge

Easyでポカミスして高順位を逃した。
https://community.topcoder.com/stat?c=problem_statement&pm=16267&rd=18601

問題

トーナメントグラフが与えられる。
異なる4頂点からなる長さ4の閉路は何通りあるか。

解法

A→X→B→Y→Aという閉路があるとして、XをYを総当たりしよう。
X→B→YとなるBとY→A→XとなるAを数え上げ、その積を取ればよい。
トーナメントグラフであるために、XとYに対し、AとB両方に相当しうる頂点はないので、そこは重複を考えなくてよい。

ループの仕方によって、各閉路複数回数え上げることになるのでその分割ることに注意。

int E[601][601];

class MarriageAndCirclingChallenge {
	public:
	ll state;
	ll rnd() {
		state = (state * 1103515245 + 12345)%(1LL<<31);
	    return state %100;
	}
	
	long long solve(int N, int threshold, int s) {
		state=s;
		
		ZERO(E);
		int i,j;
		for(i=0;i<N;i++) {
			for(j=i+1;j<N;j++) {
				if(rnd()<threshold) E[i][j]=1;
				else E[j][i]=1;
			}
		}
		ll ret=0;
		
		for(int B=0;B<N;B++) for(int C=B+1;C<N;C++) {
			int BAC=0,CAB=0;
			for(int A=0;A<N;A++) {
				if(A==B||A==C) continue;
				if(E[B][A]&&E[A][C]) BAC++;
				if(E[C][A]&&E[A][B]) CAB++;
			}
			ret+=BAC*CAB;
		}
		
		return ret/2;
		
	}
}

まとめ

配列長を間違えてエラーしてしまった。