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

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

本日解いた問題

C - Switches

C - Switches
解答

#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, ss;
  cin >> n >> m;
  vec k(m);
  vector<vector<ll>> s(m, vector<ll> (0));
  for(int i = 0; i < m; i++){
    cin >> k[i];
    for(int j = 0; j < k[i]; j++){
      cin >> ss;
      ss--;
      s[i].push_back(ss);
    }
  }
  vec p(m);
  for(int i = 0;i < m; i++) cin >> p[i];
  vector<ll> jud(m);
  ll res = 0;
  for(int bit = 0; bit < (1 << n); bit++){
    bool jud = true;
    for(int i = 0; i < m; i++){
      ll sum = 0;
      for(int j = 0; j < k[i]; j++){
        if(bit&(1<<s[i][j])) sum++;
      }
      if(sum%2!=p[i]) jud = false;
    }
    if(jud) res++;
  }
  cout << res << endl;
}

解法

bit全探索を用いて解いていく。1からNのスイッチがONかどうかで全探索を行う。

C - Average Length

C - Average Length
解答

#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 x(n), y(n);
  rep(i, n) cin >> x[i] >> y[i];
  vec o(n);
  rep(i, n) o[i] = i;
  double res = 0;
  ll cnt = 0;
  do{
    double dis = 0;
    for(int i = 0; i < n-1; i++){
      dis += sqrt((x[o[i]]-x[o[i+1]])*(x[o[i]]-x[o[i+1]]) + (y[o[i]]-y[o[i+1]])*(y[o[i]]-y[o[i+1]]));
    }
    res += dis;
    cnt++;
  } while(next_permutation(o.begin(), o.end()));
  res /= cnt;
  cout << fixed << setprecision(12);
  cout << res << endl;
}

解法

順列全探索を行い解いていく。すべての通り方において距離の計算を行い、平均値をとることで結果が求まる。

C - Count Order

C - Count Order
解答

#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;
  vec p(n), q(n);
  rep(i, n) cin >> p[i];
  rep(i, n) cin >> q[i];
  vec order(n);
  rep(i, n) order[i] = i+1;
  ll cnt = 0;
  do{
    cnt++;
    bool pjud = true, qjud = true;
    for(int i = 0; i < n; i++){
      if(p[i] != order[i]) pjud = false;
      if(q[i] != order[i]) qjud = false;
    }
    if(pjud) a = cnt;
    if(qjud) b = cnt;
  } while (next_permutation(order.begin(), order.end()));
  cout << abs(a - b) << endl;
}

解法

順列全探索を用いて解いていく。next_permutationを使うと辞書順に順列の並び替えができるため、P、Qが1からNまでの順列と一致する順番を調べることで結果が求まる。