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

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

AtCoder ABC 131 E - Friendships (500 点)

順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの

問題へのリンク

問題概要

 N 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど  K 組であるようなものを構築せよ。

存在しない場合は -1 と出力せよ。

制約

  •  2 \le N \le 100
  •  1 \le K \le N(N-1)/2

考えたこと

この手の構築を安定して解くためには、まず典型的なグラフたちに対して「最短経路長が 2 となる組数はどうなってるか」を観察するのが良さそうな気がする。そんな代表的なグラフとして

  • パス
  • スターグラフ (今回の肝...今回に限らず検討すべきグラフ!!!)
  • 完全グラフ
  • 完全二部グラフ
  • パスにちょっとヒゲを生やしたグラフ

などなど。

f:id:drken1215:20190622230718p:plain

で、例えば頂点数  N = 6 とかにして検討してみると

  • パス: 5 個
  • スターグラフ: 10 個 (なんか多い!)
  • 完全グラフ: 0 個

といったことが読み取れる。一般に

  • パス:  N-1
  • スターグラフ:  {}_{N-1}{\rm C}_{2} 個
  • 完全グラフ:0 個

ということで、

  • スターグラフはなんかいっぱい作れそう

なことが見て取れる。さらに完全グラフが 0 個というところを見て、

  • 辺を引いたところは最短距離が 1 になるので、最短距離が 2 なところに辺を引くと、そのペアを潰せる

ということまで見て取れるのだ。

答え

ここからもうほとんど答えに行き着く。とりあえず  K \le {}_{N-1}{\rm C}_{2} の場合は

  • スターグラフを作る
  •  {}_{N-1}{\rm C}_{2} - K 個の辺を追加してペアを潰す

とするだけで OK。潰せるペアはまさに最大で  {}_{N-1}{\rm C}_{2} 組あるのだ。

f:id:drken1215:20190622231302p:plain

K が大きいとき

 K 0 以上  K \le {}_{N-1}{\rm C}_{2} 以下の場合はできた。それより大きいときはできないことは念のためにちゃんと示したい。

本番ではスターグラフが最大だろうとなんとなく信じられたらそのまま提出してしまってもいいと思う。一応示してみる。

  • 頂点対は  \frac{N(N-1)}{2}
  • グラフは連結なので辺は最小でも  N-1 個ある
  • よって、最短距離 2 な組数は、どんなに大きくても  \frac{N(N-1)}{2} - (N-1) = \frac{(N-1)(N-2)}{2} 個まで

ということで意外とあっさり示せる。

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

using pint = pair<int,int>;
int main() {
    int N, K; cin >> N >> K;
    int ma = (N-1)*(N-2) / 2;
    if (ma < K) cout << -1 << endl;
    else {
        vector<pint> res;
        for (int i = 1; i <= N-1; ++i) res.push_back({i, N});
        
        int rem = ma - K;
        int ci = 1, cj = 2;
        for (int _ = 0; _ < rem; ++_) {
            res.push_back({ci, cj});
            
            ++cj;
            if (cj == N) {
                ++ci;
                cj = ci + 1;
            }
        }
        
        cout << res.size() << endl;
        for (auto p : res) cout << p.first << " " << p.second << endl;
    }
}