kmjp's blog

競技プログラミング参加記です

CSAcademy Round #40 : E. Direct the Graph

適当に書いたらあたってしまった。
https://csacademy.com/contest/round-40/task/direct-the-graph/

問題

Nが与えられる。
N頂点の完全グラフ中の各辺に向きを割り当てることを考える。
長さ3の閉路が最大となる割り当てとその数を求めよ。

解法

OEISを調べると以下が引っかかる。

"Maximal number of inconsistent triples in a tournament on n+2 nodes"
A006918 - OEIS

これを信用すると、数は簡単な計算で求められる。
また、偶奇によりなんか結果が異なることがわかる。

x<yに対し、x,yの偶奇が一致するならx→y、しないならy→xと辺を張ると、上記の結果と閉路の数が一致する辺の張り方ができた。
まぁ奇数a,bに対しx→x+a→x+a+b→xと辺が張れることになるので、閉路が増えそうではある。

ll N;
int mat[2020][2020];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N;
	ll tot=0;
	FOR(x,N) FOR(y,N) {
		if(y>x && (y-x)%2) mat[x][y]=1;
		if(y<x && (y-x)%2==0) mat[x][y]=1;
	}
	if(N%2==1) {
		tot=N*(N+1)*(N-1)/24;
	}
	else {
		tot=N*(N+2)*(N-2)/24;
	}
	
	_P("%lld\n",tot);
	FOR(x,N) for(y=x+1;y<N;y++) _P("%d",mat[x][y]);
	_P("\n");
}

まとめ

久々にOEIS使った。