AtCoder Beginner Contest 304

OKU

結果

A - First Player : AC(7:27)
B - Subscribers : AC(14:59)
C - Virus : AC(26:57)
D - A Piece of Cake : WA
E - Good Graph : WA

A - First Player

$${N}$$人の人が円卓に座っていて、時計回りの順でその人の名前$${S_{i}}$$と年齢$${A_{i}}$$が与えられる
年齢が最も小さい人を起点として時計回りに座っている人の名前を出力する問題

自分の回答

int main(){
  int N;
  cin >> N;

  queue<pair<string, int>> A;
  int mina = 1000000000;
  for(int i = 0; i < N; i++){
    string s;
    int a;
    cin >> s >> a;
    mina=min(mina, a);
    A.push({s, a});
  }

  while(A.front().second != mina){
    A.push(A.front());
    A.pop();
  }

  while(!A.empty()){
    printf("%s\n", A.front().first.c_str());
    A.pop();
  }
}

入力の時に最少年齢を調べてその人が先頭に来るまでqueueを回す

公式解説

省略

B - Subscribers

整数$${N}$$が与えられ、以下の通りに近似値を求める問題
・$${N}$$が$${10^3-1}$$以下ならば$${N}$$をそのまま出力する
・$${N}$$が$${10^3}$$以上$${10^4-1}$$以下ならば$${N}$$の一の位を切り捨てて出力する
・$${N}$$が$${10^4}$$以上$${10^5-1}$$以下ならば$${N}$$の十の位を切り捨てて出力する
・$${N}$$が$${10^5}$$以上$${10^6-1}$$以下ならば$${N}$$の百の位を切り捨てて出力する
・$${N}$$が$${10^6}$$以上$${10^7-1}$$以下ならば$${N}$$の千の位を切り捨てて出力する
・$${N}$$が$${10^7}$$以上$${10^8-1}$$以下ならば$${N}$$の一万の位を切り捨てて出力する
・$${N}$$が$${10^8}$$以上$${10^9-1}$$以下ならば$${N}$$の十万の位を切り捨てて出力する

自分の回答

int main(){
  int N;
  cin >> N;

  int dig = 100000000;
  while(true){
    if(dig == 100){
      printf("%d\n", N);
      return 0;
    }
    if(N >= dig){
      printf("%d\n",N - (N % (dig / 100)));
      return 0;
    }
    dig /= 10;
  }
}

上から見て行って後はそのまま

公式解説

int main() {
	string s;
	cin >> s;
	if (s.size() <= 3) cout << s << '\n';
	else cout << s.substr(0, 3) << string(s.size() - 3, '0') << '\n';
}

https://atcoder.jp/contests/abc304/editorial/6510より

そうか4文字目以降を0にすればいいのか

なるほど

C - Virus

$${N}$$人の人が二次元平面上に存在し、それぞれ座標$${(X_{i},Y_{i})}$$にいる
感染者からユークリッド距離で$${D}$$以内の人にうつるウイルスが人$${1}$$に感染した
感染条件を満たしている人全員が感染した時、全ての人に対して感染しているかを求める問題

自分の回答

#include <atcoder/all>
using namespace atcoder;

int main(){
  int N, D;
  cin >> N >> D;
  D *= D;
  vector<int> X(N), Y(N);
  for(int i = 0; i < N; i++){
    cin >> X[i] >> Y[i];
  }

  dsu G(N);
  for(int i = 0; i < N - 1; i++){
    for(int j = i + 1; j < N; j++){
      if((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]) <= D){
        G.merge(i, j);
      }
    }
  }

  int l = G.leader(0);
  for(int i = 0; i < N; i++){
    if(G.leader(i) == l){
      printf("Yes\n");
    }
    else{
      printf("No\n");
    }
  }
}

グラフで距離D以下の人に辺を繋げて行って人1と同じ連結成分に属しているなら感染する、そうでないならしない

公式解説

省略

D - A Piece of Cake

$${xy}$$平面上に$${N}$$個のイチゴが乗った長方形のケーキが存在する
このケーキを$${y}$$軸と並行に$${A}$$回、$${x}$$軸と並行に$${B}$$回切った
ピースに乗っているイチゴの最小個数と最大個数を求める問題

自分の回答

イチゴがどの区分に存在するか縦と横で分けてみたけどWAにTLE
いい方法は思いつかなかった

公式解説

typedef long long ll;

ll w, h;
ll n, A, B;
ll p[200001], q[200001];
ll a[200002], b[200002];

int main(void)
{
  cin >> w >> h;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> p[i] >> q[i];
  cin >> A;
  for(int i = 1; i <= A; i++) cin >> a[i];
  cin >> B;
  for(int i = 1; i <= B; i++) cin >> b[i];
  a[A+1] = w, b[B+1] = h;
  
  map<pair<ll, ll>, ll> mp;
  for(int i = 1; i <= n; i++){
    ll X = *lower_bound(a+1, a+A+2, p[i]);
    ll Y = *lower_bound(b+1, b+B+2, q[i]);
    mp[{X, Y}]++;
  }
  
  ll m = n, M = 0;
  for(auto p : mp) M = max(M, p.second);
  if(mp.size() == (A+1)*(B+1)){
    for(auto p : mp) m = min(m, p.second);
  }
  else m = 0;
  cout << m << " " << M << endl;
  
  return 0;
}

https://atcoder.jp/contests/abc304/editorial/6499より

lower_boundでどのピースに属するかを調べられるのか

これの存在は知らなかった
なるほど

E - Good Graph

$${N}$$頂点$${M}$$辺の無向グラフ$${G}$$が与えられ、頂点$${x_{i}}$$と$${y_{i}}$$を結ぶパスが$${K}$$個全てにおいて存在しない時良いグラフとする
$${Q}$$個の独立した質問「頂点$${p_{i}}$$と$${q_{i}}$$を結んだ時それは良いグラフであるか」が与えられるため判定する問題

自分の回答

どの連結成分が繋がったらアウトかをACLのleaderで調べてpqそれぞれ属する連結成分を調べてアウトかで書いてみたけどダメだった

公式解説

https://atcoder.jp/contests/abc304/editorial/6504より

基本的な考え方は合ってるっぽい？

#include <atcoder/all>
using namespace atcoder;

int main(){
  int N,M;
  cin>>N>>M;
  dsu G(N+1);
  for(int i=0;i<M;i++){
    int u,v;
    cin>>u>>v;
    G.merge(u,v);
  }
  int K;
  cin>>K;
  set<pair<int,int>> out;
  for(int i=0;i<K;i++){
    int x,y;
    cin>>x>>y;
    int xl=G.leader(x),yl=G.leader(y);
    out.insert({xl,yl});
    out.insert({yl,xl});
  }
  int Q;
  cin>>Q;
  for(int i=0;i<Q;i++){
    int p,q;
    cin>>p>>q;
    if(out.count({G.leader(p),G.leader(q)})){
      printf("No\n");
    }
    else{
      printf("Yes\n");
    }
  }
}

ダメかを二次元配列で管理してたのをsetにしたら行けた

この記事が気に入ったらサポートをしてみませんか？