AtCoder Beginner Contest 310

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

結果

A - Order Something Else : AC(5:03)(1ペナ)
B - Strictly Superior : AC(16:18)
C - Reversible : AC(35:40)
D - Peaceful Teams : 提出無し

A - Order Something Else

高橋君がレストランでドリンクを飲もうとしている
ドリンクは定価で$${P}$$円である
また、割引券を使うとドリンクを$${Q}$$円で飲むことができるがそのほかに料理を一つ注文する必要があり、料理は$${N}$$品ありそれぞれ$${D_{i}}$$円である
ドリンクを飲むために支払う合計金額の最小値を求める問題

自分の回答

int main(){
  int N, P, Q;
  cin >> N >> P >> Q;
  vector<int> D(N);
  for(int i = 0; i < N; i++){
    cin >> D[i];
  }

  sort(D.begin(), D.end());

  printf("%d\n", min(P, Q + D[0]));
}

DをソートしてPとQ+D[0]の小さい方

Qを値引く値と勘違いして1ペナ
問題文はちゃんと読もう

公式解説

省略

B - Strictly Superior

AtCoder商店には$${N}$$個の商品がありそれぞれ価格は$${P_{i}}$$で$${C_{i}}$$個の機能を持ち$${F_{i,j}}$$の機能がある
以下の条件をすべて満たす上位互換となる$${i}$$番目と$${j}$$番目の商品の組み合わせがあるかを求める問題
・$${P_{i} \geqq P_{j}}$$である
・$${j}$$番目の商品は$${i}$$番目の商品が持つ機能を全て持つ
・$${P_{i} > P_{j}}$$であるか$${j}$$番目の商品は$${i}$$番目の商品が持たない機能を一つ以上持つ

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> P(N);
  vector<set<int>> F(N);
  for(int i = 0; i < N; i++){
    int c;
    cin >> P[i] >> c;
    for(int j = 0; j < c; j++){
      int f;
      cin >> f;
      F[i].insert(f);
    }
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(i == j){
        continue;
      }
      if(P[i] >= P[j]){
        bool hig = true;
        for(int x : F[i]){
          if(!F[j].count(x)){
            hig = false;
          }
        }
        if(hig && (P[i] > P[j] || F[j].size() > F[i].size())){
          printf("Yes\n");
          return 0;
        }
      }
    }
  }
  printf("No\n");
}

そのまま

公式解説

省略

C - Reversible

英小文字からなる$${N}$$個の文字列$${S_{i}}$$が与えられ、ある文字列とそれを前後反転させた文字列を同じものとみなしたとき何種類文字列が存在するか求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  set<string> S;
  int ans = 0;
  for(int i = 0; i < N; i++){
    string s;
    cin >> s;
    string rs = s;
    reverse(rs.begin(), rs.end());

    if(!S.count(s) && !S.count(rs)){
      ans++;
      S.insert(s);
      S.insert(rs);
    }
  }

  printf("%d\n", ans);
}

sとそれを反転したrsを作って両方無いなら種類を1増やして両方setに入れる

公式解説

省略

D - Peaceful Teams

$${N}$$人のスポーツ選手がいる
互いに相性の悪いペアが$${M}$$組存在し、それは$${A_{i}}$$番目と$${B_{i}}$$番目の選手である
選手を$${T}$$チームに分けるが、全員がいずれかのチームに属し、全てのチームには一人以上選手が属している必要がある。また、相性の悪い全てのペアは二人が同じチームに属してはいけない
この条件を満たすチーム分けは何通りあるか求める問題

自分の回答

相性を無視した組み合わせの総数は第二種スターリング数で求められることがわかったからそこからペアが同じチームに属している組み合わせの数を引くのかなと思ったけどそこの数え上げ方が思いつかなかった
あと制約的に組み合わせを総当たりしても大丈夫そうだったけどいい感じに組み合わせを出す方法も思いつかなかった

公式解説

unsigned N, T, M;
vector<unsigned> hate, teams;

// 再帰関数でチーム分け
unsigned dfs(unsigned now) {
    // 最後の選手まで見て T チームに分かれていれば OK
    if (now == N)
        return size(teams) == T;

    unsigned ans{};

    // すでにあるチームに now 番目の選手を追加する
    for (auto &&team : teams)
        // チームに now 番目の選手と相性の悪い選手がいなければ
        if (!(team & hate[now])) {
            team ^= 1U << now;
            ans += dfs(now + 1);
            team ^= 1U << now;
        }

    // チーム数に余裕があるとき、新しいチームを作る
    if (size(teams) < T) {
        teams.emplace_back(1U << now);
        ans += dfs(now + 1);
        teams.pop_back();
    }

    return ans;
}

int main() {
    using namespace std;
    cin >> N >> T >> M;

    // hate[i] の j ビットめが 1 ⟹ i 番目の選手と j 番目の選手の相性が悪い (0-indexed)
    hate = vector<unsigned>(N);
    for (unsigned i{}, a, b; i < M; ++i) {
        cin >> a >> b;
        hate[--b] |= 1U << --a;
    }

    teams.reserve(T);
    cout << dfs(0) << endl;

    return 0;
}

https://atcoder.jp/contests/abc310/editorial/6783より

そうか深さ優先探索は総当たりだったか

なるほど