Codeforces ECR #009 : F. Magic Matrix

終わってみればゴリ押しが解っぽい？
http://codeforces.com/contest/632/problem/F

問題

N次正方行列Aが与えられる。
Aがmagicであるとは以下をすべて満たす状態をいう。
Aがmagicかどうか判定せよ。

• 対称行列である。
• 対角成分は0である。
• 各i,j,kについて、A_ij ≦ max(A_ik,A_jk)を満たす。

解法

対称性と対角成分はまず最初に処理しよう。

Aの要素を小さい順にソートし、順に上の3つめの条件を満たすか判定する。
各行に対し、各列がすでに処理済み(すなわち以降の要素より小さい要素を持つ)かどうかをN bitのbitsetで管理する。
例えばそのようなbitsetをB[i]とする。

A_ijに対し、B[i]&B[j]が1bitでも立てば、A_ik・A_jkがともにA_ijより小さいようなkが存在することになり、magicでないことが判定できる。
結構TLが厳しいので、少しでも無駄な処理をしないようにしよう。
以下のコードでは4.7s程度かかる。

int N;
int A[2525][2525];
bitset<2525> R[2525];
vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) FOR(x,N) cin>>A[y][x];
	FOR(x,N) if(A[x][x]) return _P("NOT MAGIC\n");
	FOR(y,N) FOR(x,N) if(A[y][x]!=A[x][y]) return _P("NOT MAGIC\n");
	FOR(y,N) FOR(x,y) V.push_back({A[y][x],(y<<15)+x});
	sort(ALL(V));
	
	i=j=0;
	while(i<V.size()) {
		while(j<V.size() && V[j].first==V[i].first) {
			y=V[j].second>>15;
			x=V[j].second&0x3FFF;
			auto B=R[y] & R[x];
			if(B.any()) return _P("NOT MAGIC\n");
			j++;
		}
		while(i<j) {
			y=V[i].second>>15;
			x=V[i].second&0x3FFF;
			R[y].set(x,1);
			R[x].set(y,1);
			i++;
		}
	}
	
	_P("MAGIC\n");
}

まとめ

Nは2000上限でも良かったんじゃないかな…。