ABC131E -Freindship

問題

atcoder.jp

N頂点の単純かつ無向グラフで最短距離が２であるような頂点対がちょうどK個あるようなものがあるかを判別し、あれば一例を出力する問題です。入力はN<=100　Kです。

検討

問題の意味は理解できましたがどのように解いていっていいのかわかりませんでした。

解説で距離２のペアの最小値（完全グラフの場合で０）、最大値（いわゆるウニ(in english , it may called "Star")の場合で(n-2)(n-1)/2）がわかること、ウニの葉に順に辺を貼っていくと０までの間の任意のKを設定できることがわかりました。

下準備 pairの使い方　pairを要素とするvectorの入力と出力

方針は理解できましたが実装が難しそうです。

ウニの各辺のエッジを出力するところをまず準備しました。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int main(){
  int N;
  cin>>N;
  vector<P> edge;
  for(int i=0;i<N-1;i++){
    for(int j=0;j<i;j++){
      edge.push_back(P(i+1,j+1));
    }
  }
  for(int i=0;i<edge.size();i++){
    cout<<edge[i].first<<" "<<edge[i].second<<endl;
  }
  return 0;
}

入力例

5

出力例

2 1
3 1
3 2
4 1
4 2
4 3

違う書き方

出力のところをイテレーターを使って書いてみました。

  for(auto itr=edge.begin();itr != edge.end();itr++){
     cout<<itr->first<<" "<<itr->second<<endl;
  }

出力のところを範囲for文を使って書いてみました。

  for(auto &e :edge){
     cout<<e.first<<" "<<e.second<<endl;
  }

ACしました。

一から改めて自力で書いてみました。
無事ACしました。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;

int main(){
  int N,K;
  cin>>N>>K;
  if(!(0<=K && K<=(N-2)*(N-1)/2)){
    cout<<-1<<endl;
    return 0;
  }
 
  vector<P>ans;
  //ウニの構築
  for(int i=2;i<=N;i++){
    ans.push_back({1,i});
  }
  //ちょうどK個になるよう減らす
  vector<P>ve;
  for(int i=2;i<=N;i++){
    for(int j=i+1;j<=N;j++){
      ve.push_back({i,j});
    }
  }
  for(int i=0;i<(N-2)*(N-1)/2-K;i++){
    ans.push_back(ve[i]);
  }
  
  cout<<ans.size()<<endl;
  for(int i=0;i<ans.size();i++){
    cout<<ans[i].first<<" "<<ans[i].second<<endl;
  }
 
  return 0;
}

pairの入力について

pairの入力についてよく悩みます。
この機会に整理してみました。

{}でくくる

最近多用しているのはこの書き方です。

 ans.push_back({1,i});

型名pairをつけて入力

解説で提出されていたコードではこんな形でした。

 ans.push_back(P(1,i));

Pはtypedefしたpairなので普通に書けばこうでしょうか。

 ans.push_back(pair<int,int>(1,i));

いずれも問題なくACしました。

make_pairを使う

他の方の提出されているコードでは、make_pairを使っているものがありました。
これも問題なくACします。

 ans.push_back(make_pair(1,i));

それぞれ厳密には違いがあったりするのかも知れませんが、まずは問題なく入力できる形をしっかりと身につけたいと思います。