AGC032 B. Balanced Neighbors

Difficulty:1259

問題

N頂点の単純連結無向グラフであって、各頂点から隣接する頂点番号の総和が等しいようなものを一つ構築せよ。

解法

実験をすると、完全グラフから各頂点1つずつ取り除いたもの（Nが偶数の場合は2つずつ取り除いたもの）が答えになることがわかるので、それをそのまま実装すればよい。

実装

code:cpp

bool solve(){

LL(n);

vector<pair<ll,ll>>ans;

if(n%2==1){

rep(i,1,n+1){

rep(j,1,n+1){

if(i>=j)continue;

if(n-i==j)continue;

ans.push_back({i,j});

}

}

}

else{

rep(i,1,n+1){

rep(j,1,n+1){

if(i>=j)continue;

if(n-j+1==i)continue;

ans.push_back({i,j});

}

}

}

O(ans.size());

return false;

}