AtCoder abc310 参加メモ

freee Programming Contest 2023（AtCoder Beginner Contest 310） - AtCoder

B - Strictly Superior

全探索。p[i] == p[j] の場合など条件がややこしいため注意する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,m; cin >> n >> m;
  vector<int> p(n),c(n);
  vector f(n,vector<bool>(m));
  REP(i,n) {
    cin >> p[i] >> c[i];
    REP(j,c[i]) {
      int x; cin >> x; x--;
      f[i][x] = true;
    }
  }

  REP(i,n) REP(j,n) {
    if (i == j) continue;
    if (p[i] > p[j]) continue;
    bool ok = true;
    int cnt = 0; // i のみにある機能の個数
    REP(k,m) {
      if (f[j][k] && !f[i][k]) ok = false;
      if (f[i][k] && !f[j][k]) cnt++;
    }
    if (p[i] == p[j]) ok = ok && cnt > 0;
    if (ok) { cout << "Yes" << endl; return 0; }
  }

  cout << "No" << endl;
  return 0;
}

C - Reversible

set を使って通常と逆順両方がまだ集合になかったら追加する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  unordered_set<string> st;

  REP(i,n) {
    string s; cin >> s;
    if (st.count(s)) continue;
    reverse(s.begin(),s.end());
    if (st.count(s)) continue;
    st.insert(s);
  }

  cout << st.size() << endl;
  return 0;
}

D - Peaceful Teams

DFS。

チームは区別されないので、まだ誰もいないチームに人を入れるときには、一つのチームだけで良い(この場合どの空のチームに入れても区別されないため)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,t,m; cin >> n >> t >> m;
  vector c(n,vector<int>(n)); // c[i][j] := i,j の相性が悪いかどうか
  REP(i,m) {
    int a,b; cin >> a >> b;
    a--; b--;
    c[a][b] = c[b][a] = 1;
  }

  vector g(t,vector<int>()); // チームに所属しているメンバー情報
  auto dfs = [&](auto self, int i) -> int {
    if (i == n) {
      REP(j,t) if (g[j].size() == 0) return 0;
      return 1;
    }

    int res = 0;
    REP(j,t) {
      bool ok = true; // j チームに i を追加可能かどうか
      for(auto v: g[j]) if (c[i][v]) ok = false;
      if (!ok) continue;

      g[j].push_back(i);
      res += self(self,i+1);
      g[j].pop_back();
      if (g[j].size() == 0) break;
    }
    return res;
  };

  cout << dfs(dfs, 0) << endl;
  return 0;
}

今回の成績

tic40さんのfreee プログラミングコンテスト2023（AtCoder Beginner Contest 310）での成績：1772位
パフォーマンス：1315相当
レーティング：1174→1189 (+15) :)
Highestを更新しました！
#AtCoder #freeeプログラミングコンテスト2023（ABC310） https://atcoder.jp/users/tic40/history/share/abc310?lang=ja