AtCoder 勉強記録[C++] その29

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
私のアカウント
解いた問題

本日解いた問題

B - Ancestor

B - Ancestor
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n;
  cin >> n;
  vec p(n);
  for(int i = 1; i < n; i++){
    cin >> p[i];
  }
  ll tmp = p[n-1];
  ll res = 1;
  while(tmp != 1){
    tmp = p[tmp-1];
    res++;
  }
  cout << res << endl;
}

解法

N番目の人の親からある人の親が1番目になるまで探索していくことで結果が求まる。

B - Triangle (Easier)

B - Triangle (Easier)
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n, m;
  cin >> n >> m;
  vector<vector<bool>> g(n, vector<bool>(n));
  for(int i = 0; i < m; i++){
    ll a, b;
    cin >> a >> b;
    a--, b--;
    g[a][b] = g[b][a] = true;
  }
  ll res = 0;
  for(int i = 0; i < n-2;i++){
    for(int j = i+1; j < n-1; j++){
      for(int k = j+1; k < n; k++){
        if(g[i][j]&&g[j][k]&&g[k][i]) res++;
      }
    }
  }
  cout << res << endl;
}

解法

UiとViを結ぶ線分が存在するかどうかを入れておく配列gを用意しておく。abcにおいて線分が存在するかどうかを全探索することで結果が求まる。

C - X drawing

C - X drawing
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  ll p, q, r, s;
  cin >> p >> q >> r >> s;
  string str="";
  vector<string> res;
  for(ll i = 0; i < s-r+1; i++) str += '.';
  for(ll i = 0; i < q-p+1; i++) res.push_back(str);
  ll ksta = max(p-a, r-b);
  ll kend = min(q-a, s-b);
  for(ll i = ksta; i <= kend; i++){
    res[a+i-p][b+i-r] = '#';
  }
  ksta = max(p-a, b-s);
  kend = min(q-a, b-r);
  for(ll i = ksta; i <= kend; i++){
    res[a+i-p][b-i-r] = '#';
  }
  for(ll i = 0; i < q-p+1; i++) cout << res[i] << endl;
}

解法

問題の条件を言い換えると、1つ目の条件はMAX(P-A,R-B)<=k<=MIN(Q-A,S-B)と言い換えられ、2つ目の条件はMAX(P-A,B-S)<=k<=MIN(Q-A,B-R)と言い換えることができる。この条件でマスを黒く塗ることで結果が求まる。

C - Graph Isomorphism

C - Graph Isomorphism

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll a, b, n, m;
  cin >> n >> m;
  vector<vector<bool>> gt(n, vector<bool>(n));
  vector<vector<bool>> ga(n, vector<bool>(n));
  for(int i = 0; i < m; i++){
    cin >> a >> b;
    a--,b--;
    gt[a][b] = true;
    gt[b][a] = true;
  }
  for(int i = 0; i < m; i++){
    cin >> a >> b;
    a--,b--;
    ga[a][b] = true;
    ga[b][a] = true;
  }
  vec o(n);
  for(int i = 0; i < n; i++) o[i] = i;
  do {
    bool jud = true;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(gt[i][j] != ga[o[i]][o[j]]) jud = false;
      }
    }
    if(jud) {
      cout << "Yes" << endl;
      exit(0);
    }
  }while(next_permutation(o.begin(), o.end()));
  cout << "No" << endl;
}

解法

ボール同士を結ぶ線分が存在するかどうかを入れておく配列を高橋君の場合と青木君の用意しておく。順列全探索を用いてすべての並べ方において、高橋君のボールi,jが結ばれているとき、青木君のボールPi,Pjが結ばれているかを判定することで結果が求まる。