Good Bye 2021: F. Tricolor Triangles

本番中に解きたかった。
https://codeforces.com/contest/1616/problem/F

問題

N点M辺のグラフが与えられる。
一部の辺には、3色のうちいずれかの色が塗られている。
残りの辺に、それぞれ3色のいずれかで塗りたい。
ただし、長さ3の閉路は、色がいずれも異なるか、いずれも一致しないといけない。

可能なら、塗り分け方の一例を示せ。

解法

閉路に関する条件は、言い換えると3辺の色番号の和が3の倍数であると同義である。
とすると、長さ3の閉路を列挙することで、3変数の方程式がたくさんできるので、掃き出し法の要領で各辺の色を定められる。

int T,N,M;
int A[303],B[303],C[303];
int D[303][303];

const int MAT=2556;
ll mo=3;
ll ma[5000][MAT],V[MAT],R[MAT];
ll rev(ll a, ll n = mo-2) {
	return a;
}

int Gauss(int n,int m,ll mat_[5000][MAT],ll v_[MAT],ll r[MAT]) { //m変数n式
	int i,j,k;
	static ll mat[5000][MAT],v[MAT];
	memmove(mat,mat_,sizeof(mat));
	memmove(v,v_,sizeof(v));
	int cur=0;

	FOR(i,m) {
		r[i]=0;
		for(j=cur;j<n;j++) if(mat[j][i]) break;
		if(j>=n) continue;
		FOR(k,m) swap(mat[cur][k],mat[j][k]);
		swap(v[cur],v[j]);
		
		(v[cur]*=rev(mat[cur][i]))%=mo;
		FOR(k,i) assert(mat[cur][k]==0);
		for(k=m-1;k>=i;k--) (mat[cur][k]*=rev(mat[cur][i]))%=mo;
		FOR(j,n) if(j!=cur&&mat[j][i]) {
			v[j]=((v[j]-v[cur]*mat[j][i]%mo)+mo)%mo;
			for(k=m-1;k>=i;k--) mat[j][k]=((mat[j][k]-mat[cur][k]*mat[j][i]%mo)+mo)%mo;
		}
		cur++;
	}
	
	FOR(i,n) {
		
		FOR(j,m) if(mat[i][j]) break;

		if(j<m) r[j]=v[i];
		else if(v[i]) {
			return -1;
		}
	}
	return cur;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		MINUS(D);
		ZERO(ma);
		ZERO(V);
		ZERO(R);
		int cur=0;
		
		FOR(i,M) {
			cin>>A[i]>>B[i]>>C[i];
			A[i]--,B[i]--;
			D[A[i]][B[i]]=D[B[i]][A[i]]=i;
			
			if(C[i]>=0) {
				ma[cur][i]=1;
				V[cur]=C[i]-1;
				cur++;
			}
		}
		FOR(k,N) FOR(y,k) FOR(x,y) if(D[x][y]>=0&&D[x][k]>=0&&D[y][k]>=0) {
			ma[cur][D[x][y]]=ma[cur][D[y][k]]=ma[cur][D[x][k]]=1;
			V[cur]=0;
			cur++;
		}
		x=Gauss(cur,M,ma,V,R);
		if(x==-1) {
			cout<<-1<<endl;
		}
		else {
			FOR(i,M) cout<<R[i]+1<<" ";
			cout<<endl;
		}
		
	}
}

まとめ

なぜ気付かなかったか…。