AtCoder ABC #258 : G - Triangle

賞金とかないときに限って調子いいな。上位陣の参加者が少ないだけかもしれないけど。
https://atcoder.jp/contests/abc258/tasks/abc258_g

問題

N頂点の無向グラフが与えられる。
長さ3の閉路はいくつあるか。

解法

bitsetを使うとO(N^3)で通ってしまう。
以下のように辺をbitsetで持とう。
E[v] := 長さNのbool列で、i番目の要素は頂点iとvの間に辺があるかどうかを示す
辺でつながれた頂点対u-vに対し、E[u] & E[v]のbitcountは、u-vと合わせて長さ3の閉路を成す頂点の集合となる。

int N;
bitset<3200> E[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>s;
		FOR(x,N) E[y][x]=s[x]=='1';
	}
	ll ret=0;
	FOR(y,N) {
		FOR(x,y) if(E[y][x]) ret+=(E[y]&E[x]).count();
	}
	cout<<ret/3<<endl;
	
}

まとめ

これ想定解じゃないとは思うけど、多くの人bitsetで通してそう。