ABC049 ARC065 の問題を解いてみました

A問題

if文で a, i, u, e, o かどうかを判定します。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  char ch;
  cin >> ch;
  
  if(ch == 'a' || ch == 'i' || ch == 'u' || ch == 'e' || ch == 'o'){
    //判定する
    cout << "vowel" << endl;
  }
  else{
    cout << "consonant" << endl;
  }
  
}

B問題

1行読み込んだら、その行を2回出力する という処理を行います。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  int h, w;
  cin >> h >> w;
  char picture[h][w];
  
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cin >> picture[i][j];
      cout << picture[i][j]; // 一回目の出力
    }
    cout << endl; //改行
    for(int j = 0; j < w; j++){
      cout << picture[i][j]; // 二回目の出力
    }
    cout << endl; //改行
  }
}

C問題

そのまま作れるかを調べると、 dreamerase などの文字列には対応しづらいです。
文字列を反転させて 文字列$S$ を作れるかを調べましょう。

下の記事が詳しく解説してくれているので、見てみてください。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

//maerd remaerd esare resare
int main(void){
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  string li[4] = {"maerd", "remaerd", "esare", "resare"};
  //反転させた文字列を用意する
  
  bool ok = true;
  for(int i = 0; i < s.size();){
    bool can = false;
    for(int j = 0; j < 4; j++){
      string a = li[j];
      if(s.substr(i, a.size()) == a){ //対応する文字列があるか
        can = true;
        i += a.size();
        break;
      }
    }
    if(!can){
      ok = false;
      break;
    }
  }
  
  if(ok) cout << "YES" << endl;
  else cout << "NO" << endl;
}

D問題

まず、都市$i$と都市$j$がつながっているかをすべて調べていると、$O(N^2)$でTLEしてしまいます。
なので、より高速な方法を考えます。

この問題は、2つの無向グラフどちらでも連結している都市の数を数えるというグラフ問題です。
このような無向グラフの問題では、UnionFindが使えます。
UnionFindでは、親の番号が同じならば、その2点は連結しているといえます。
つまり、2つのUnionFindどちらでも親の番号が一緒な都市を、pairを使ったmapなどで数えればよいです。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#include <atcoder/all>
using namespace atcoder;
//Created by karaju.


signed main(){
  int n, k, l;
  cin >> n >> k >> l;
  
  dsu road(n), rail(n); //用意
  
  for(int i = 0; i < k; i++){
    int p, q;
    cin >> p >> q;
    p--; q--;
    road.merge(p, q);
    //都市を道路でくっつける
  }
  for(int i = 0; i < l; i++){
    int r, s;
    cin >> r >> s;
    r--; s--;
    rail.merge(r, s);
    //都市を鉄道でくっつける
  }
  
  map<pair<int,int>,int> cnt;
  for(int i = 0; i < n; i++){
    cnt[{road.leader(i), rail.leader(i)}]++;
    //road.leader(i)で、道路でくっついていない都市をふるい落として
    //rail.leader(i)で、鉄道でくっついていない都市をふるい落として
    //最終的にどちらでも連結な都市の数を数えるイメージ
  }
  
  for(int i = 0; i < n; i++){
    cout << cnt[{road.leader(i), rail.leader(i)}] << " ";
  }
  
  cout << endl;
  
}