AGC032 B - Balanced Neighbors (700)

B - Balanced Neighbors

概要

N頂点の無向グラフで各頂点に１からNの番号付けがされてあり、下記の条件を持たすものを答えよ。

• 単純かつ連結
• あるSが存在し、任意の頂点について隣接する頂点の和がS

（解答はグラフの辺数・グラフの辺を出力する）

制約

3 ≦ N ≦ 100

方針

張りうる辺をすべて張った状態（いわゆる完全グラフ）で、各頂点について隣接頂点の和を計算してみる。
N = 5 であれば、下記の通り。

頂点	和
1	14
2	13
3	12
4	11
5	10

ここから辺(1, 4), (2, 3)を取り除くと各頂点の隣接頂点の和はすべて10になる。

N = 6 の場合は、頂点と和の関係は下記の通り。

頂点	和
1	20
2	19
3	18
4	17
5	16
6	15

この場合は辺(1, 6), (2, 5), (3, 4)を取り除くことにより、各頂点の隣接頂点の和がすべて14になる。

任意のNについても、奇数の場合・偶数の場合で分けて上記の考え方を適用すればよい。

感想

2完ー！初めてコンテストで700解けた！

— misora192 (@misora192) March 23, 2019

コンテスト中は、Nが小さい方から試していき、N=4は自力で発見しました。
N=5は思いつかなかったのですが、いろいろ試しているなかで、辺全部張ったグラフで合計計算して眺めていたら、上記解答を思いつきました。

解答

Submission #4675010 - AtCoder Grand Contest 032

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	if(N % 2 == 0){
		cout << N * (N - 1) / 2 - N / 2 << endl;
		for(int i = 1; i <= N; i++){
			for(int j = i + 1; j <= N; j++){
				if(i + j == N + 1) continue;
				cout << i << " " << j << endl;
			}
		}
	}else{
		cout << N * (N - 1) / 2 - (N-1)/ 2 << endl;
		for(int i = 1; i <= N; i++){
			for(int j = i+1; j <= N; j++){
				if(i + j == N) continue;
				cout << i << " " << j << endl;
			}
		}
	}
 
 
}