AtCoder ARC #207 (AtCoder Japan Open -予選-) : B - Balanced Neighbors 2

だいぶ手間取ってしまった…。
https://atcoder.jp/contests/arc207/tasks/arc207_b

問題

正整数Nが与えられる。
以下を満たす連結無向単純グラフが作れるなら一例を示せ。

• 各点は1～Nのラベルを持つとする。
• 各点vにおいて、最短距離が1または2の点のラベルの値の総和は等しい

解法

d(u,v) := 2点u,v間の最短距離
とする。

まずNが偶数の時を考える。
点u,vに対し、d(u,v)=3となるのはu+v=N+1の時だけとなるようにすれば、上記ラベルの値の総和は常に2+3+...+(N-1)で一致する。
そのため、点1～(N/2)と点(N/2)+1～Nで構成される完全二部グラフから、u+v=N+1となる2点間の辺を削除すればよい。

Nが奇数の時は、和がNとなる2点間の辺を除けばよい。

int N,M;
int D[25][25];

int E[202][202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N<=5) {
		cout<<-1<<endl;
		return;
	}
	FOR(x,N) FOR(y,N) E[x][y]=(x==y)?0:1010;
	FOR(x,N) FOR(y,N) {
		if(x==y) continue;
		if(N%2==0) {
			if(x+y==N-1) continue;
		}
		else {
			if(x+y==N-2) continue;
		}
		if(x<N/2&&y>=N/2)  E[x][y]=E[y][x]=1;
	}
	FOR(k,N) FOR(x,N) FOR(y,N) E[x][y]=min(E[x][y],E[x][k]+E[k][y]);
	set<int> S={0};
	FOR(y,N) {
		int sum=0;
		FOR(x,N) if(E[x][y]==1||E[x][y]==2) sum+=x+1;
		S.insert(sum);
		
	}
	assert(S.size()==2);
	
	vector<pair<int,int>> E2;
	FOR(x,N) FOR(y,N) if(x<y&&E[x][y]==1) E2.push_back({x+1,y+1});
	cout<<E2.size()<<endl;
	FORR2(a,b,E2) cout<<a<<" "<<b<<endl;
	
	
	
}

まとめ

本番は総当たりとかして色々手間取った。