読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

SRM 682 Div1 easy : SmilesTheFriendshipUnicorn

問題概要 :
N人の人がいて、それらの人は0からN-1まで順に番号が割り振られている
これらの人の間には友好関係があり、これは2つの整数で表される
友好関係は2つの配列A,Bとして表されA[i]番の人とB[i]番の人は友達である
A[i] != B[i]
これらの友好関係は無向グラフとして表すことができる
このとき、任意の2頂点間には必ずパスが存在する
このグラフ内に長さが4のパスが存在するか、YESかNOで答えよ
つまり、5つの異なる頂点a,b,c,d,eについて、
aとb,bとc,cとd,dとeに辺が存在する

解法 :
無向グラフ内から下の図のような部分が存在するかを判定したい
f:id:tei3344:20160223133648p:plain
このとき、
f:id:tei3344:20160223133744p:plain
すぐ上の図の赤い枠で囲まれた辺をループで愚直に決めてしまう
赤い枠で囲まれた辺は2本しかないので、2000 * 2000 で4つの頂点からなる長さ3のパスを求めることができる
残り1つの頂点は長さ3のパスの両端点について、次数からO(1)で計算できる

まず2つの辺から長さ3のパスを計算する
f:id:tei3344:20160223134116p:plain
以下の4通りのパスが存在する
f:id:tei3344:20160223134203j:plain
f:id:tei3344:20160223134217j:plain
f:id:tei3344:20160223134233j:plain
f:id:tei3344:20160223134252j:plain

この各4通りのパスについて、端点に1つ頂点が追加できれば求めたいパスになる
これは次数からO(1)で計算できる
先ほどの1つめの例で考えると、
f:id:tei3344:20160223134506j:plain
2番か4番の頂点から5番に辺があれば良い
2番の頂点に注目したとき、5番の頂点というのは1,3,4番の頂点でなければどれでもよい
つまり、2番の頂点の次数をdegとしたとき、
2-1に辺は必ず存在するので --deg
2-3に辺が存在するなら --deg
2-4に辺が存在するなら --deg
この結果が1以上であれば、1でも3でも4でもない頂点と2は繋がっている
これを5とすればよい

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const string kzy = "Yay!";
const string KT  = ":(";

struct Edge {
  int s,t;
  bool operator < (const Edge& e) const {
    if( s != e.s ) return s < e.s;
    return t < e.t;
  }
};

bool rel[2010][2010];
vector<int> G[2010];

class SmilesTheFriendshipUnicorn {
public:

  bool check(Edge e1,Edge e2,bool sp1,bool sp2) {
    int p1 = -1, p2 = -1;
    int rp1 = -1, rp2 = -1;
    if( sp1 ) p1 = e1.t, rp1 = e1.s;
    else      p1 = e1.s, rp1 = e1.t;
    if( sp2 ) p2 = e2.t, rp2 = e2.s;
    else      p2 = e2.s, rp2 = e2.t;
    if( !rel[p1][p2] ) return false;
    
    int deg1 = (int)G[rp1].size();
    int deg2 = (int)G[rp2].size();
    
    //
    --deg1;
    if( rel[rp1][p2] ) --deg1;
    if( rel[rp1][rp2] ) --deg1;
    if( deg1 >= 1 ) return true;
    
    //
    --deg2;
    if( rel[rp2][p1] ) --deg2;
    if( rel[rp2][rp1] ) --deg2;
    if( deg2 >= 1 ) return true;
    
    return false;
  }

   string hasFriendshipChain( int N, vector <int> A, vector <int> B ) {
     N = N;
     vector<Edge> vec;
     rep(i,(int)A.size()) {
       vec.push_back((Edge){A[i],B[i]});
       G[A[i]].push_back(B[i]);
       G[B[i]].push_back(A[i]);
       rel[A[i]][B[i]] = rel[B[i]][A[i]] = true;
     }
     rep(i,(int)vec.size()) {
       Edge &e1 = vec[i];
       rep(j,(int)vec.size()) {
         Edge &e2 = vec[j];
         if( e1.s == e2.s || e1.s == e2.t ) continue;
         if( e1.t == e2.s || e1.t == e2.t ) continue;
         if( check(e1,e2,0,0) ) return kzy;
         if( check(e1,e2,0,1) ) return kzy;
         if( check(e1,e2,1,0) ) return kzy;
         if( check(e1,e2,1,1) ) return kzy;
       }
     }
     
     return KT;
   }
};