Balanced Neighborsに対する考察(AtCoder Grand Contest 032 B)

問題

問題はこちら。

atcoder.jp

簡単な紹介から。
$1$ ~ $N$ までの番号がついた $N$ 頂点の無向グラフがあって以下の条件を満たすようなグラフを出力する。

単純かつ連結（単純とは、多重辺・自己ループを含まないこと）
任意の頂点について、隣接する頂点に書かれた値の和が $s$ になるように $s$ を設定することができる。

入力： $N$
出力：辺の本数とそれぞれの辺が結んでいる頂点

問題を理解することは簡単だ。さてこれをどう解いていくかが問題だ。

考察

極端な例をまず考える。

全ての頂点が1直線上に並んでいる場合

一直線上に並んだ頂点の左から $k$ 番目の頂点を $a_k$ とする。頂点 $a_{k-1}$ 、 $a_{k+1}$ に隣接する頂点を考える。条件２を考えると、
$a_{k-2} + a_k = a_k + a_{k+2}$ 、つまり $a_{k-2} = a_{k+2}$ となる。
異なる二つの頂点に描かれた番号が一致することはないので、この場合は不適。

円形になっている場合

上の場合と全く同じで不適。

全ての頂点同士が辺で結ばれている場合

頂点 $i$ について、隣接している頂点の番号の和は $\ s = n \times (n + 1) \ / \ 2 - i$
となり、条件が満たされない。
しかし、グラフを生成する方法として、全ての頂点がつながった状態から辺を落としていくこともできる。果たしてどの辺を落とすのがいいだろうか。

考察を伸ばす

頂点の番号の和が等しくなるようなペアを作ることを考える(ペアを作るといったらまずこれを考えるのは自分だけ？）。例えば $N$ = $4$ の時、{(1, 4), (2, 3)}のようなペアを作ることができる。今 $N$ が偶数の時だけを考えているが（奇数にすると一つ余る）、まあいいだろう。このペア間の辺を落としてみる。

f:id:horoyoisawa:20200319114705p:plain — 辺を落とした後のグラフ

上のような状態になる。隣接する頂点の和を考えてみると、全て $5$ になってみていい感じ。偶数の場合はこれで良さそうである。
ここまでわかればあとは簡単である。奇数の場合は頂点 $N$ を除外して上のように考える。それから頂点 $N$ と残りの頂点全てを結ぶ。各和に $N$ が足されるだけなので、条件は満たしたままである。
（奇数の場合を考えるのにめっちゃ時間を使った。。）

提出コード

こちらから。
atcoder.jp

#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  int n; 
  cin >> n;
  vector<vector<int>> edge(n);
  rep(i, n) {
    rep(j, n) {
      if(i == j) continue;
      if(n % 2 == 0 && i + j == n - 1) continue;
      if(n % 2 == 1 && i + j == n - 2) continue;
      edge[i].emplace_back(j);
    }    
  }      
  if(n % 2 == 0) cout << n * (n - 2) / 2 << endl;
  else cout << (n - 1) * (n - 3) / 2 + n - 1 << endl;
  rep(i, n) {
    for(auto& node : edge[i]) {
      if(i > node) continue;
      cout << i+1 << ' ' << node + 1 << endl;
    }    
  }      
  return 0;
}

感想

本当こういう思いつき問題って本当に手を動かさないとわからないから色々考える力が試される（これで「考える」とか言っていたら後の問題とか相当きついが）。わかったら面白いし、実装は非常に簡単なので一瞬で終わる問題。
解き終わった後の素直な感想：「極端な例から考えるのはすごい役に立つ」

ではまた。

horoyoisawaのゴミ箱

いろいろ書きます