Codeforces #609 Div1 D. Invertation in Tournament

実装はともかく考察が難しい。
https://codeforces.com/contest/1268/problem/D

問題

N頂点のトーナメントグラフが与えられる。
頂点vを選ぶと、vを端点とする全辺の向きを反転できる。

この処理を繰り返し、グラフ全体を強連結にしたい。
最小処理回数と、選ぶ点の順番の組み合わせは何通りかを求めよ。

解法

理由はEditorialを参照してもらうとして、N＞6では最大1頂点に処理を施せば必ず条件を満たすものが1つはある。
そこで全頂点を総当たりすればよい。

これで達成できないケースは、N=4で解がない場合と、N=6で3点の完全グラフが2つくっついているケースで2頂点選ぶ選び方のみである。

int N;
string S[2020];
string T[2020];
int deg[2020];

int scc() {
	int D[2020];
	int i;
	FOR(i,N) D[i]=deg[i];
	sort(D,D+N);
	int sum=0;
	FOR(i,N-1) {
		sum+=D[i]-i;
		if(sum==0) return 0;
	}
	return 1;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		FOR(j,N) deg[i]+=S[i][j]-'0';
	}
	
	if(scc()) {
		cout<<0<<" "<<1<<endl;
		return;
	}
	
	int ret=0;
	FOR(i,N) {
		FOR(j,N) if(i!=j) {
			if(S[i][j]=='1') deg[i]--, deg[j]++;
			else deg[i]++, deg[j]--;
		}
		if(scc()) {
			ret++;
		}
		FOR(j,N) if(i!=j) {
			if(S[i][j]=='0') deg[i]--, deg[j]++;
			else deg[i]++, deg[j]--;
		}
	}
	
	if(ret) {
		cout<<1<<" "<<ret<<endl;
		return;
	}
	
	if(N==4) {
		cout<<-1<<endl;
	}
	else if(N==6) {
		cout<<2<<" "<<18<<endl;
	}
	
}

まとめ

この性質本番中に詰めるの難しくない？と思ったらやっぱりDの本番ACはわずかだった。