三角形、四角形、、、と順に作って行って、五角形の場合を作るのに苦労した!!!
問題概要
頂点番号が な単純無向であって、以下の条件を満たすものを 1 つ構築せよ:
- どの頂点についても、その頂点に隣接している頂点の番号の和が等しい
制約
考えたこと
こういうのはとりあえず手を動かして、三角形、四角形、五角形...と作りながら様子を見るのがいいと思う。
三角形
四角形
五角形
これ気づくの苦労した。まさか五角形の「ノード 5」から全部引っ張るのがいいとは思わなかった。。。
思ったこと
ここまで実験していると、
- 奇数角形では「最大ノードから全体に枝を引っ張る」
- 偶数各系では「最大ノードから 1 を除いたノードに枝を引っ張る」
とするのがよいのでは、という予想がついた。そしてさらに、考察を進めると、例えば四角形では
- ノード 4 は「1 以外」
- ノード 3 は「2 以外」
- ノード 2 は「3 以外」
- ノード 1 は「4 以外」
という風にしていることに気づいた。五角形では
- ノード 5 は「全部」
- ノード 4 は「1 以外」
- ノード 3 は「2 以外」
- ノード 2 は「3 以外」
- ノード 1 は「4 以外」
となっている。つまりどちらにしても、
- ノード番号が小さくなるにつれて、除去するものを増やしている
という感じ。これはよくよく考えるとそれはそうで「完全グラフ」を考えたとき、例えば五角形では
- ノード 5 の隣接は 10 (= 15- 5)
- ノード 4 の隣接は 11 (= 15-4)
- ノード 3 の隣接は 12 (= 15-3)
- ノード 2 の隣接は 13 (= 15-2)
- ノード 1 の隣接は 14 (= 15-1)
という感じになっているので、そこから順に「0, 1, 2, 3, 4」を引くようにすると丁度全ノードについて和が等しくなるのだ!!!!!
あとは何故偶数奇数によって分かれるかであるが、
- ノード v は「v 以外につなぐ」
というのは無効なので、そういう状態が発生しないようにしないといけないからで。
#include <iostream> #include <vector> using namespace std; using pint = pair<int,int>; int main() { int N; cin >> N; vector<pint> res; int dame = N; if (N % 2 == 1) --dame; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { if (j <= i || j == dame) continue; res.push_back(pint(i, j)); } --dame; } cout << res.size() << endl; for (auto p : res) { cout << p.first << " " << p.second << endl; } }