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

ferinの競プロ帳

競プロについてのメモ

ABC022を解いてみた

競技プログラミング ABC

abc022.contest.atcoder.jp

A問題

 N日目のとき、適正体重かどうかを判定しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int n=0, s=0, t=0, w=0, a[1000], ans=0;
  cin >> n >> s >> t;
  cin >> w;
  for(int i=1; i<n; ++i) cin >> a[i];

  if(s <= w && w <= t) ++ans;
  for(int i=1; i<n; ++i)
  {
    w += a[i];
    if(s <= w && w <= t) ++ans;
  }

  cout << ans << endl;

  return 0;
}

B問題

 たどった花の種類別に数を数えて2個以上になった種類は、その数-1が受粉するという方針で実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_N 100000

int main(void)
{
  int n=0, a=0, lis[MAX_N]={}, ans=0;
  cin >> n;
  for(int i=0; i<n; ++i)
  {
    cin >> a;
    lis[a-1] += 1;
  }

  for(int i=0; i<MAX_N; ++i)
  {
    //if(i < 30) cout << "lis: " << lis[i] << endl;
    if(lis[i] >= 2) ans += (lis[i]-1);
  }

  cout << ans << endl;
  return 0;
}

 

C問題

 もっとも短い経路の閉路を探すアルゴリズムが思いつかなかったので解説見て実装しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 999999999
#define MAX_N 300

int main(void)
{
  //lis1が1に隣接する頂点へのコスト
  int n, m, u, v, l, d[MAX_N][MAX_N]={}, lis1[MAX_N]={}, ret = 0, minret = INF;
  //lisが1に隣接する頂点番号のリスト
  vector<int> lis;
  bool flag = true;

  // dの初期化
  fill( d[0], d[MAX_N], INF);
  for(int i=1; i<MAX_N; ++i) d[i][i] = 0;

  //入力
  cin >> n >> m;
  for(int i=0; i<m; ++i)
  {
    cin >> u >> v >> l;
    if(u != 1 && v != 1) {d[u-1][v-1] = l; d[v-1][u-1] = l;}
    else if(u == 1) {lis1[v-1] = l; lis.push_back(v);}
    else {lis1[u-1] = l; lis.push_back(u);}
  }

  //ワーシャルフロイド
  // d[i][j] で頂点iから頂点jへの最短距離
  for(int k=0; k<n; ++k) {
    for(int i=0; i<n; ++i) {
      for(int j=0; j<n; ++j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }

  // lis の中から2つを選択
  for(int i=0; i < lis.size()-1; ++i) {
    for(int j=i+1; j < lis.size(); ++j) {
      ret = lis1[lis[i]-1] + lis1[lis[j]-1] + d[lis[i]-1][lis[j]-1];
      //cout << "lis[i]:" << lis[i]-1 << " lis[j]:" << lis[j]-1 << " lis1[lis[i]]" << lis1[lis[i]-1] << " lis1[lis[j]]" << lis1[lis[j]-1] << " d" << d[lis[i]-1][lis[j]-1] << " ret:" << ret << endl;
      minret = min(minret, ret);
    }
  }

  //たどり着けるパターンがなかったら-1を出力
  if(minret == INF) minret = -1;
  cout << minret << endl;

  return 0;
}

D問題

 回転行列を使ってやるのかなとか考えてても実装方法が思い浮かばなかったので、解説見て実装しました。N点の重心と最遠点の比率による方法をつかいました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define MAX_N 100000

int main(void)
{
  int n, ax[MAX_N], ay[MAX_N], bx[MAX_N], by[MAX_N];
  double agx=0.0, agy=0.0, bgx=0.0, bgy=0.0, adist=0.0, bdist=0.0, maxadist=0.0, maxbdist=0.0;

  cin >> n;
  for(int i=0; i<n; i++) cin >> ax[i] >> ay[i];
  for(int i=0; i<n; i++) cin >> bx[i] >> by[i];

  for(int i=0; i<n; i++) {
    agx += ax[i]; agy += ay[i];
    bgx += bx[i]; bgy += by[i];
  }
  agx /= n; agy /= n;
  bgx /= n; bgy /= n;

  //cout << agx << " " << agy << " " << bgx << " " << bgy << endl;

  for(int i=0; i<n; i++) {
    adist = pow(ax[i] - agx, 2) + pow(ay[i] - agy, 2);
    maxadist = max(maxadist, adist);
    bdist = pow(bx[i] - bgx, 2) + pow(by[i] - bgy, 2);
    maxbdist = max(maxbdist, bdist);
  }

  //cout << "maxa:" << maxadist << " maxb:" << maxbdist << endl;
  cout << setprecision(12) << sqrt(maxbdist)/sqrt(maxadist) << endl;

  return 0;
}