AGC032 B - Balanced Neighbors

グラフを考えて隣接してるものの和を一定にする問題。
問題は以下。

考察

グラフを0から繋いで書こうとしても場合が多すぎて、Nが多くなったとき一般化できなさそう
↓
隣接する和Sの最小値は、Nが一個だけ繋がってるときのNで、
最大値は、Nの頂点がすべてとつながっている場合で1~N-1までの和でN*(N-1)*1/2。
よって
和Sとして考えられる個数は
N<=S<=N*(N-1)*1/2
より
N*(N-3)*1/2 + 1（個）。

全探索してもいいかもしれないけど、グラフ自体の繋ぎ方が組合せ爆発を起こしそう。

↓

グラフの繋がりは総当たり戦（隣接行列というらしい）みたいな表を作れば
考えられそう

↓
N=3のサンプル、N=4は実験でこのようにするのが良い
f:id:coonevo:20190324025615j:plain

完全に繋いだとき（完全グラフというらしい）の和をmaxとして書いておくと、
繋がないとしたときのマイナスの値が上の方が大きくなれば良さそうだということがわかる

これをN=6でも書いてみても同じで
f:id:coonevo:20190324025615j:plain
こうなるので、これを実装してあげればいい。
Nの偶奇で表の規則性が変わるので、それに注意して実装。

コードは以下。
Submission #4678361 - AtCoder Grand Contest 032

#include <bits/stdc++.h>
using namespace std;

#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)


typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

vector<int> Iv;
vector<int> Jv;
int N;
int main() {
	cin>>N;
	int X = N;
	if(N%2 == 0)X = N+1;

	int cnt =0;
	rep1(i,N+1)rep1(j,N+1){
		if(i<j)if(i+j!=X){
			cnt++;
			Iv.push_back(i);
			Jv.push_back(j);
		}
	}

	cout<<cnt<<endl;

	rep(i,cnt){
		cout<<Iv[i]<<' '<<Jv[i]<<endl;
	}
}

ながめも

競技プログラミングについて

AGC032 B - Balanced Neighbors