AtCoder Beginner Contest 284

AtCoder Beginner Contest 284 - AtCoder

結果

A - Sequence of Strings:AC(1:50)
B - Multi Test Cases:AC(4:53)
C - Count Connected Components:AC(21:13)
D - Happy New Year 2023:AC(39:29)(3ペナ)
E - Count Simple Paths:提出無し

A - Sequence of Strings

$${N}$$個の文字列が与えられ、それを逆順で出力する問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }

  for(int i = N - 1; i >= 0; i--){
    printf("%s\n", S[i].c_str());
  }
}

そのまま

公式解説

省略

B - Multi Test Cases

$${T}$$個のテストケースが与えられ、テストケース1つは$${N}$$個の整数$${A_{1},A_{2},…,A_{N}}$$からなる
この中に奇数がいくつあるかを全てのテストケースに対して求める問題

自分の回答

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

  for(int i = 0; i < T; i++){
    int n;
    cin >> n;

    int odd = 0;
    for(int j = 0; j < n; j++){
      int a;
      cin >> a;
      if(a % 2 == 1){
        odd++;
      }
    }
    printf("%d\n", odd);
  }
}

そのまま

公式解説

省略

C - Count Connected Components

頂点に$${1}$$から$${N}$$の番号が、辺に$${1}$$から$${M}$$の番号がついた$${N}$$頂点$${M}$$辺の単純無向グラフが与えられ、辺$${i}$$は頂点$${u_{i}}$$と頂点$${v_{i}}$$を結んでいる
グラフに含まれる連結成分の個数を求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> G(N + 1, vector<int>());
  for(int i = 0; i < M; i++){
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  vector<bool> vis(N + 1, false);
  int ans = 0;
  for(int i = 1; i <= N; i++){
    if(vis[i]){
      continue;
    }

    queue<int> bfs;
    bfs.push(i);
    vis[i] = true;
    while(!bfs.empty()){
      for(int x : G[bfs.front()]){
        if(vis[x]){
          continue;
        }
        bfs.push(x);
        vis[x] = true;
      }
      bfs.pop();
    }
    ans++;
  }
  printf("%d\n",ans);
}

頂点1から順に、その頂点がすでに調査したグラフに入っていたらスルー、入っていなかったらその頂点を起点として幅優先探索してそのグラフに含まれる頂点を全て調べ、連結成分数をプラス

公式解説

省略

D - Happy New Year 2023

$${T}$$個の正整数$${N}$$が与えられ、$${N}$$は2つの相異なる素数$${p,q}$$を用いて$${N=p^2q}$$と表すことができる
全ての$${N}$$に対して$${p,q}$$を求める問題

自分の回答

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

  for(int i = 0; i < T; i++){
    int64_t n;
    cin >> n;
    int64_t p, q;
    for(int64_t i = 2; i * i < n; i++){
      if(n % i != 0){
        continue;
      }
      else{
        n /= i;
        if(n % i == 0){
          p = i;
          q = n / i;
        }
        else{
          p = sqrt(n);
          q = i;
        }
        printf("%ld %ld\n", p, q);
        break;
      }
    }
  }
}

素因数が2つと確定しているから素因数分解していって1つ見つかったら1回nをiで割った後、さらにnをiで割った余りが無ければiがpのためqはn/i、余りがあればiはqのためnの平方根がpと求められるため出力して次のNへ

素因数を1つ見つければ良くて、その小さい方は素因数は相異なるという条件を無視しても最大$${\sqrt[3]{N}}$$だから計算量は$${\sqrt[3]{N}}$$になるのかな
breakしなかったらTLEするのかな

出力がp qの順であることを見逃して1ペナ、p,qがintの外になることがあるのを見逃したり出力を%ldにし忘れて2ペナ

公式解説

using ll = long long;

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        
        ll p = 0, q = 0;
        for (ll i = 2; i * i * i <= n; i++) {
            if (n % i != 0) continue;
            if ((n / i) % i == 0) {
                p = i;
                q = n / i / i;
            } else {
                q = i;
                p = (ll) round(sqrt(n / i));
            }
            break;
        }
        cout << p << ' ' << q << endl;
    }
}

https://atcoder.jp/contests/abc284/editorial/5467より

そうかforの範囲は$${i^3<=n}$$まででいいのか
それとT回やるのそんな方法もあるのか

E - Count Simple Paths

頂点に$${1}$$から$${N}$$の番号が、辺に$${1}$$から$${M}$$の番号がついた$${N}$$頂点$${M}$$辺の単純無向グラフが与えられ、辺$${i}$$は頂点$${u_{i}}$$と頂点$${v_{i}}$$を結んでいる、また、各頂点の次数は10以下である
頂点1を始点とする単純パスの個数を$${K}$$とし、min($${K,10^6}$$)を求める問題

自分の回答

深さ優先探索で行けるかと書いてみたけどグラフ内にループする部分があると通った場所の管理がめんどくさくなるからどうしたもんかと悩んで終わり
最後の方に頂点と辺の数から求められるのではと思ったけど具体的なことはわからなかった

公式解説

int calc(int N, vector<vector<int>> g) {
  int ans = 0, limit = 1000000;
  vector<int> vis(N);
  auto dfs = [&](auto rc, int c) -> void {
    if (ans == limit) return;
    ans++;
    vis[c] = true;
    for (auto& d : g[c]) {
      if (vis[d]) continue;
      rc(rc, d);
    }
    vis[c] = false;
  };
  dfs(dfs, 0);
  return ans;
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> g(N);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  cout << calc(N, g) << "\n";
}

https://atcoder.jp/contests/abc284/editorial/5494より

そうか深さ優先探索は同じルートを2回通ることは無いから今どこを踏んでいるのかをチェックすればいいのか
これはプログラムの動きをしっかり理解できていなかったな