けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 032 B - Balanced Neighbors (700 点)

三角形、四角形、、、と順に作って行って、五角形の場合を作るのに苦労した!!!

問題へのリンク

問題概要

頂点番号が  1, 2, \dots, N な単純無向であって、以下の条件を満たすものを 1 つ構築せよ:

  • どの頂点についても、その頂点に隣接している頂点の番号の和が等しい

制約

  •  3 \le N \le 100

考えたこと

こういうのはとりあえず手を動かして、三角形、四角形、五角形...と作りながら様子を見るのがいいと思う。

三角形

f:id:drken1215:20190324103056p:plain

四角形

f:id:drken1215:20190324103234p:plain

五角形

これ気づくの苦労した。まさか五角形の「ノード 5」から全部引っ張るのがいいとは思わなかった。。。

f:id:drken1215:20190324105302p:plain

思ったこと

ここまで実験していると、

  • 奇数角形では「最大ノードから全体に枝を引っ張る」
  • 偶数各系では「最大ノードから 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;
    }
}