適当に書いたらあたってしまった。
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使った。