AtCoder Grand Contest 032 B

atcoder.jp

問題文

整数 N が与えられます。 頂点に 1 から N の番号がついた N 頂点の無向グラフであって、以下の 2 つの条件を満たすものを 1 つ構成してください。

• 単純かつ連結
• ある整数 S が存在して、任意の頂点についてその頂点に隣接する頂点の番号の値の和は S となる

この問題の制約下でそのようなグラフが少なくとも 1 つ存在することが証明できます。

制約

• 入力は全て整数である。
• 

出力

1行目に構成したグラフの辺の本数を出力せよ。 続く行のうち行目には、2つの整数とを出力せよ。これらは番目の辺の端点を表す。 構成されたグラフが条件を満たすならば正解となる。

解法

この問題は、任意の頂点Vについてつながっていない頂点(自身含む)の番号の和を一定にすること、と言い換えが出来る。 隣接行列を描いて考える。

• N=偶数の場合

• N=奇数の場合

偶数と同様に考える 対処法

上の図で色のついていないマスが求める辺になる。

C++で実装

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<pair<int, int>> ans;

void read()
{
    cin >> N;
}
void solve()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if ((i + j) != (N + 1 - (N & 1)))
            {
                ans.push_back(make_pair(i, j));
            }
        }
    }
}
void print()
{
    cout << ans.size() << endl;
    for (auto &&i : ans)
    {
        cout << i.first << " " << i.second << endl;
    }
}
int main()
{
    read();
    solve();
    print();
    return 0;
}