活動日記 day 30

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

A - Best Body
実際にN日間の第10の変化を計算してベストボディーである日を数えます。
コード :

#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;
 
int n,s,t;
int w;
 
int main() {
  int cnt = 0;
  cin >> n >> s >> t;
  cin >> w;
  int cur = w;
  if( s <= cur && cur <= t ) ++cnt;
  rep(i,n-1) {
    int a;
    cin >> a;
    cur = cur + a;
    if( s <= cur && cur <= t ) ++cnt;
  }
  cout << cnt << endl;
  return 0;
}

B - Bumble Bee
i番目より前に訪れた花の種類を配列等で保持し、i番目の花の種類がすでに存在するかどうかを判定します。
コード :

#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;
 
int n, A[100010];
bool found[100010];
 
int main() {
  cin >> n;
  int cnt = 0;
  rep(i,n) {
    cin >> A[i];
    if( found[A[i]] ) ++cnt;
    found[A[i]] = true;
  }
  cout << cnt << endl;
  return 0;
}

C - Blue Bird
答えとなる閉路は家１を端点に持つ辺をちょうど２本含みます。
そのため、家１から出ている辺を全て取り除いた状態のグラフの全点間の最短経路をワーシャルフロイドやdijkstraで求めた後に
どの２つの辺を答えとなる閉路に含めるか全パターン試します。
コード :

#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;
 
struct Edge {
  int t,v;
};
 
struct Data {
  int cur, c;
  bool operator < ( const Data & data ) const {
    if( c != data.c ) return c > data.c;
    return cur < data.cur;
  }
};
 
int V,E;
vector<Edge> G[400];
vector<int> ID[400];
int mini[400];
 
int dijkstra(int e) {
  rep(i,V) mini[i] = INT_MAX;
  int dst = G[0][e].t;
  if( dst == 0 ) return INT_MAX;
  mini[0] = 0;
  priority_queue<Data> Q;
  Q.push((Data){0,0});
  while(!Q.empty()) {
    Data d = Q.top(); Q.pop();
    if( d.cur == dst ) return d.c + G[0][e].v;
    rep(i,(int)G[d.cur].size()) {
      int nex = G[d.cur][i].t;
      if( ID[d.cur][i] == ID[0][e] )  continue;
      if( mini[nex] > d.c + G[d.cur][i].v ) {
	mini[nex] = d.c + G[d.cur][i].v;
	Q.push((Data){nex,mini[nex]});
      }
    }
  }
  return INT_MAX;
}
 
void compute() {
  int ans = INT_MAX;
  rep(i,(int)G[0].size()) {
    ans = min(ans,dijkstra(i));
  }
  if( ans == INT_MAX ) puts("-1");
  else cout << ans << endl;
}
 
int main() {
  cin >> V >> E;
  rep(i,E) {
    int s,t,v;
    cin >> s >> t >> v;
    --s, --t;
    G[s].push_back((Edge){t,v});
    G[t].push_back((Edge){s,v});
    ID[s].push_back(i);
    ID[t].push_back(i);
  }
  compute();
  return 0;
}

D - Big Bang
問題文中の処理を行ったとしても、その点集合において変化しない情報について考えます。
例えば、最も近い２点は処理後も変化しません。
そのため、処理前と処理後の最も近い２点間の距離を求め、処理後の距離で処理前の距離を割ればPが求まります。
その他にも、点集合の凸包をとってできた凸多角形の重心と各点との距離からもPを求めることができます。
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
 
using namespace std;
 
struct Point { 
  int x,y; 
  bool operator < ( const Point &p ) const {
    if( x != p.x ) return x < p.x;
    return y < p.y;
  }
};
 
#define MAX 100010
 
bool cmp_y(const Point &a,const Point &b) {
  return a.y < b.y;
}
 
//#define pow2(x) ((x)*(x))
//double mydist(Point a,Point b) { return sqrt(pow2(a.x-b.x)+pow2(a.y-b.y)); }
 
double mydist(Point a,Point b) { 
  //double dx = ((a.x - b.x)*(a.x-b.x));
  //double dy = ((a.y - b.y)*(a.y-b.y));
  double dx = (a.x - b.x);
  double dy = (a.y - b.y);
  dx = dx * dx;
  dy = dy * dy;
  return sqrt(dx+dy);
  //return sqrt(dx+dy); 
}
 
double closest_pair(Point *ps,int n) {
  if( n <= 1 ) return INT_MAX;
  int m = n / 2;
  double x = ps[m].x;
  double d = min(closest_pair(ps,m),closest_pair(ps+m,n-m));
  inplace_merge(ps,ps+m,ps+n,cmp_y);
  vector<Point> vec;
  rep(i,n) {
    if( fabs(x-ps[i].x) >= d ) continue;
    for(int j=(int)vec.size()-1;j>=0;--j) {
      double dy = fabs(ps[i].y-vec[j].y);
      if( dy >= d ) break;
      d = min(d,mydist(ps[i],vec[j]));
    }
    vec.push_back(ps[i]);
  }
  return d;
}
 
int n;
Point A[MAX], B[MAX];
 
void compute() {
  sort(A,A+n);
  double mini1 = closest_pair(&A[0],n);
  sort(B,B+n);
  double mini2 = closest_pair(&B[0],n);
  printf("%.10f\n",mini2/mini1);
}
 
int main() {
  cin >> n;
  rep(i,n) cin >> A[i].x >> A[i].y;
  rep(i,n) cin >> B[i].x >> B[i].y;
  compute();
  return 0;
}

E - ロミオとジュリエット
木の直径を求めれば良いです。
木の直径の求め方はday 27のセットにも出ましたね。
コード :

#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;
 
#define MAX_V 100010
 
int V;
vector<int> G[MAX_V];
 
typedef pair<int,int> ii;
 
ii visit(int p,int v) {
  ii r(0,v);
  rep(i,(int)G[v].size()) {
    int e = G[v][i];
    if(e != p) {
      ii t = visit(v,e);
      t.first += 1;
      if(r.first < t.first) r = t;
    }
  }
  return r;
}
 
int diameter() {
  ii r = visit(-1,0);
  ii t = visit(-1,r.second);
  cout << r.second + 1 << " " << t.second + 1 << endl;
  return t.first;
}
 
int main() {
  cin >> V;
  rep(i,V-1) {
    int s,t;
    cin >> s >> t;
    --s, --t;
    G[s].push_back(t);
    G[t].push_back(s);
  }
  diameter();
  return 0;
}