執筆時レート：水色

問題文→https://atcoder.jp/contests/abc301/tasks/abc310_d
公式解説→https://atcoder.jp/contests/abc301/tasks/abc310_d/editorial

問題

$N$ 個の商品がある．
各商品には価格と機能が以下のように定義されている．

商品 $i$ の価格は $P_{i}$
商品 $i$ の機能は $C_{i}$ 個あり， $j$ 番目の機能は $1$ 以上 $M$ 以下の整数 $F_{i,j}$ として表される

このとき，以下の条件を全て満たすような商品 $i$ ，商品 $j$ の組は存在するか？

$P_{i} \geq P_{j}$
商品 $j$ は商品 $i$ がもつ機能をすべてもつ
$P_{i} > P_{j}$ であるか，商品 $j$ は商品 $i$ にない機能を $1$ つ以上もつ

制約

$2 \leq N \leq 100$
$1 \leq M \leq 100$
$1 \leq P_{i} \leq {10}^{5}$
$1 \leq C_{i} \leq M$
$1 \leq F_{i,1} \lt F_{i,2} ... \lt F_{i,C_{i}} \leq M$
入力は全て整数

解説

まずは全探索を考えるのが基本．
全ての組 $(i,j)$ について，問題文の条件を全て満たすものがあるか調べる．

問題文の条件が何を意味しているのかが分からないときは，言葉で表現してみると分かりやすくなるかも．

$P_{i} \geq P_{j}$

これは「商品 $j$ の方が安いか，同じ価格」．

商品 $j$ は商品 $i$ のもつ機能をすべてもつ

これはそのままの意味．
「商品 $j$ は商品 $i$ 以上に多機能」とも言い換えられる．

$P_{i} > P_{j}$ であるか，商品 $j$ は商品 $i$ にない機能を $1$ つ以上もつ

価格については「商品 $j$ の方が安い」ということ．
機能についてはそのままの意味だが，二つ目の条件を満たしているときは，「商品 $j$ の機能 $=$ 商品 $i$ の機能 $+ α$ 」，つまり「商品 $j$ の方が多機能」ということになる．

このような3条件を全て満たす組があるか調べれば良い．

計算量はどうだろう．
調べる組み合わせの数は $O(N^{2})$ で，ある組 $(i,j)$ について各条件の判定に，

$P$ の比較をすれば良いので $O(1)$
商品 $i$ の各機能が商品 $j$ に含まれているか素朴に調べて $O(M^{2})$
価格の比較も機能数の比較も $O(1)$ なので，合わせて $O(1)$

これだと全体の計算量は， $O(N^{2}M^{2})$ となり，今回の制約だとまあ間に合うかな，という感じ．(C++の処理の速さを信じて)
他の言語だと間に合わないかもしれないし，定数倍がこわいときは，set(集合に対して所属判定を $\log (サイズ)$ で行える構造体)を使えば高速化が図れる．
具体的には，判定では $O(M^{2})$ がボトルネックになっているので，商品 $j$ の機能をまとめたsetに対して商品 $i$ の各機能が含まれているかを調べれば，判定は $O(M \log M)$ ，全体で $O(N^{2}M \log M)$ になる．

さらに，各商品について「あり得る $M$ 個の機能のうち持っているものにフラグを立てる」という管理をすれば，二つ目の条件の判定を $O(M)$ ，全体で $O(N^{2}M)$ に落とせる．

実装

$O(N^{2}M^{2})$ 解法．余裕で間に合う．
提出

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

int main(){
  // 入力を受け取る
  int n,m; cin>>n>>m;
  vector<int> p(n);
  vector<vector<int>> func(n);
  for(int i=0; i<n; i++) {
    cin>>p[i];
    int c;cin>>c;
    for(int j=0; j<c; j++) {
      int f; cin>>f;
      func[i].push_back(f);
    }
  }

  // 判定
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(p[i]>=p[j]){
        // 一つ目の条件を満たしている

        // 二つ目の条件「商品jが商品iの機能をすべて含んでいるか」を調べる
        bool inc=true; // 商品iの機能をすべて含むか？
        for(auto fi: func[i]) {
          // 商品iのある機能fiが商品jにあるか？
          bool exist=false;
          for(auto fj: func[j]) {
            if(fi==fj) exist=true;
          }

          // 無ければすべて含んでいないということ
          if(!exist) inc=false;
        }
        if(!inc) continue;

        // ここまでで二つ目の条件を満たしている
        // 最後の条件を満たすか調べる
        if(p[i]>p[j] || func[i].size()<func[j].size()) {
          // すべての条件を満たしている！
          cout<<"Yes"<<'\n';
          return 0;
        }

      }
    }
  }

  // すべての組を調べても無かった
  cout<<"No"<<'\n';

  return 0;
}

setを使った $O(N^{2}M \log M)$ 解法．
提出

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

int main(){
  // 入力を受け取る
  int n,m; cin>>n>>m;
  vector<int> p(n);
  vector<set<int>> func(n);
  for(int i=0; i<n; i++) {
    cin>>p[i];
    int c;cin>>c;
    for(int j=0; j<c; j++) {
      int f; cin>>f;
      func[i].insert(f);
    }
  }

  // 判定
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(p[i]>=p[j]){
        // 一つ目の条件を満たしている

        // 二つ目の条件「商品jが商品iの機能をすべて含んでいるか」を調べる
        bool inc=true; // 商品iの機能をすべて含むか？
        for(auto fi: func[i]) {
          // 商品iのある機能fiが商品jに無ければ，すべて含んでいないということ
          if(!func[j].count(fi)) inc=false;
        }
        if(!inc) continue;

        // ここまでで二つ目の条件を満たしている
        // 最後の条件を満たすか調べる
        if(p[i]>p[j] || func[i].size()<func[j].size()) {
          // すべての条件を満たしている！
          cout<<"Yes"<<'\n';
          return 0;
        }

      }
    }
  }

  // すべての組を調べても無かった
  cout<<"No"<<'\n';

  return 0;
}

$O(N^{2}M)$ 解法．
提出

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

int main(){
  // 入力を受け取る
  int n,m; cin>>n>>m;
  vector<int> p(n);
  vector<int> c(n);
  vector<vector<bool>> func(n,vector<bool>(m));
  for(int i=0; i<n; i++) {
    cin>>p[i]>>c[i];
    for(int j=0; j<c[i]; j++) {
      int f; cin>>f;
      f--;
      func[i][f]=true;
    }
  }

  // 判定
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(p[i]>=p[j]){
        // 一つ目の条件を満たしている

        // 二つ目の条件「商品jが商品iの機能をすべて含んでいるか」を調べる
        bool inc=true; // 商品iの機能をすべて含むか？
        for(int k=0; k<m; k++) {
          // 機能kを商品iはもっているが商品jはもっていなければ，すべて含んでいないということ
          if(func[i][k] && !func[j][k]) inc=false;
        }
        if(!inc) continue;

        // ここまでで二つ目の条件を満たしている
        // 最後の条件を満たすか調べる
        if(p[i]>p[j] || c[i]<c[j]) {
          // すべての条件を満たしている！
          cout<<"Yes"<<'\n';
          return 0;
        }

      }
    }
  }

  // すべての組を調べても無かった
  cout<<"No"<<'\n';

  return 0;
}

アジの開きを閉じる。

競プロ(AtCoder)中心のブログ

【解説】ABC310 B - Strictly Superior

問題

制約

解説

実装