AtCoder Beginner Contest 272

2022年10月11日 15:33

結果

A - Integer Sum:AC(1:46)
B - Everyone is Friends:AC(25:28)
C - Max Even:AC(39:13)
D - Root M Leaper:提出なし

A - Integer Sum

$${N}$$個の整数が与えられ、その総和を求める問題

自分の回答

int main() {
  int N;
  cin >> N;
  int sum = 0;
  for(int i = 0; i < N; i++){
    int A;
    cin >> A;
    sum += A;
  }

  printf("%d\n",sum);
}

問題文の通りに

公式解説

同じため省略

B - Everyone is Friends

$${1 ～ N}$$の番号がついた$${N}$$人の人が存在し、$${M}$$回舞踏会が行われ$${i(1 \leqq i \leqq M)}$$回目には$${k_{i}}$$人が参加し、参加した人の番号が与えられる
全てのペアが少なくとも1回同じ舞踏会に参加したかを判定する問題

自分の回答

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<bool>> P(N, vector<bool> (N, false));
  for(int i = 0; i < M; i++){
    int k;
    cin >> k;
    vector<int> pa(k);
    for(int j = 0; j < k; j++){
      cin >> pa[j];
    }
 
    for(int l = 0; l < k - 1; l++){
      for(int m = l + 1; m < k; m++){
        P[pa[l] - 1][pa[m] - 1] = true;
        P[pa[m] - 1][pa[l] - 1] = true;
      }
    }
  }
 
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(i == j){
        continue;
      }
      
      if(P[i][j] == false){
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
}

どのペアが同じ舞踏会に参加したかを二次元配列で管理
1回の舞踏会で参加した人のペアを総当たりしてそこをtrueにしていき、全部の舞踏会でそれをしたら配列を全て調べて終わり

公式解説

同じため省略

C - Max Even

長さ$${N}$$の非負整数列が与えられ、その要素から2つを取り出した和が偶数の中で最大のものを出力する問題

自分の回答

int main() {
  int N;
  cin >> N;
  vector<int64_t> even, odd;
  for(int i = 0; i < N; i++){
    int64_t A;
    cin >> A;
    if(A % 2 == 0){
      even.push_back(A);
    }
    else{
      odd.push_back(A);
    }
  }
 
  if(even.size() <= 1 && odd.size() <= 1){
    printf("-1\n");
    return 0;
  }
 
  sort(even.begin(), even.end());
  sort(odd.begin(), odd.end());

  int e_size = even.size();
  int o_size = odd.size();
  if(e_size <= 1){
    printf("%ld\n", odd[o_size - 1] + odd[o_size - 2]);
    return 0;
  }
  if(o_size <= 1){
    printf("%ld\n", even[e_size - 1] + even[e_size - 2]);
    return 0;
  }
  printf("%ld\n", max(even[even.size() - 1] + even[even.size() - 2], odd[odd.size() - 1] + odd[odd.size() - 2]));
}

2つの整数の和が偶数となるのは偶数+偶数か奇数+奇数の時なため、要素を偶数と奇数に分けて偶数の大きい順に2つの和と奇数の大きい順に2つの和の大きい方を出力

偶奇それぞれ大きいの2つだけが重要だからわざわざ配列でやらない方がコード見やすくなったかな
出力部分がだいぶひどい
あと要素が最大$${10^9}$$なのを見て反射でint64_tにしたけど2つの和だから$${2×10^9-1}$$にしかならなくてint内で収まるな

公式解説

int main() {
    int n;
    cin >> n;
    vector<int> odd, even;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if(a & 1)
            odd.push_back(a);
        else
            even.push_back(a);
    }
    sort(odd.rbegin(), odd.rend());
    sort(even.rbegin(), even.rend());
    int mx = -1;
    if(odd.size() >= 2) mx = max(mx, odd[0] + odd[1]);
    if(even.size() >= 2) mx = max(mx, even[0] + even[1]);
    cout << mx << endl;
}

基本は同じだけど出力部分そうすればよかったのか
出力用の値mxを初期値-1で配列の要素数が2以上なら大きい値2つを足してmxと比較
配列のソートも降順にすれば0と1番目か

なるほど

D - Root M Leaper

$${N×N}$$のマス目があり、現在の位置から距離が$${\sqrt{M}}$$のマスへ移動する操作を何回でも繰り返せる
初期位置が$${(1,1)}$$なとき、全てのマスについて最短何回で移動できるかを求める問題

自分の回答

何マス移動するかはマス数で2重forかけて総当たりして調べる
どのマスに何回で移動できるかは幅優先探索でだと思ったけど探索の部分がうまく書けなかった

このあたりは経験値だなぁ

公式解説

https://atcoder.jp/contests/abc272/editorial/4978より

コードが無いから細部がわからないが
何マス移動できるかを求める→全てのマスに対してどのマスへ移動できるかを求める→幅優先探索
でいいのかな

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> grid(N, vector<int>(N, -1));
  vector<pair<int, int>> Move;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      if (i * i + j * j == M){
        Move.push_back({i, j});
        Move.push_back({-i, j});
        Move.push_back({i, -j});
        Move.push_back({-i, -j});
      }
    }
  }

  map<pair<int, int>, set<pair<int, int>>> nextG;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      for (auto M : Move){
        int MX = i + M.first;
        int MY = j + M.second;
        if (MX < 0 || MY < 0 || MX >= N || MY >= N){
          continue;
        }
        else{
          nextG[{i, j}].insert({MX, MY});
        }
      }
    }
  }

  queue<pair<int, int>> next;
  grid[0][0] = 0;
  next.push({0, 0});
  while (!next.empty()){
    int nowX = next.front().first;
    int nowY = next.front().second;
    next.pop();

    for (auto NG : nextG[{nowX, nowY}]){
      if (grid[NG.first][NG.second] == -1){
        next.push(NG);
        grid[NG.first][NG.second] = grid[nowX][nowY] + 1;
      }
    }
  }

  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      printf("%d", grid[i][j]);
      if (j == N - 1){
        printf("\n");
        continue;
      }
      else{
        printf(" ");
      }
    }
  }
}

一応ACできたけどこんな感じかな

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