ABC310 B - Strictly Superior 簡易解説 - 競プロっておいしいの？(仮)

ABC310 - B の簡易解説

公式解説があまりにむずかしく見えたのでC++の実装方針と解説をおいておきます。

もし役立ったらTwitterでリンク共有するなりしてね、僕が喜ぶよ

問題概要

ざっくりいうと、ある商品Aに着目したときに、

Aの機能を全部持っていて、値段が安い商品
Aの機能を全部持っていて、Aと同じ値段なのに、Aにない機能を持っている商品

のどっちかの条件を満たす商品Bはありますか？という問題です。

つまり、(Aの値段)≧(Bの値段)であってほしいということですね。

値段が等しいときは機能を一つでも多くほしくて、安ければ機能は同じものが欠けなくすべてあればOKという感じですね！

方針説明

基本方針

今回は $N$ が最大100 なので、 $N^2$ をしても間に合いそうです。

ということで、商品Aと商品Bを全探索しましょう！

ここで kind[i] とは i 番目の商品が何の機能を持っているかを集めたものです。 kind[i].size() で何個の機能があるかを知れるというものだとしましょう。(後ほど説明します。)

すると、問題文の入力変数をそのまま使ったとするとこんな感じになります。

for(int i = 0; i < N; i++){   //  商品Aは i 番目、
  for(int j=0; j < N ; j++){  // 商品Bは j 番目とする
    if(i==j)continue;         //AとBが同じ商品のときはスキップ
    if(P[i] < P[j])continue;  //Bの方が値段が高いときはスキップ

    bool f=true;
    // f=true  Aの機能のすべてをBがもってる
    // f=false Aの機能のうちBが持ってないものがある として

    // ここに Aの機能 を Bが全部 持っているか判定を書く

    if(!f)continue; // 条件満たさないので次へ
    if(P[i]>P[j] || kind[j].size()>kind[i].size() ){
      cout<<"Yes"<<endl;
      return 0; //見つかったのでプログラムをここで終える
    }
  }
}
cout<<"No"<<endl; //見つからなかったときだけここに来る。

機能判定のパート

Q, Aの機能をBが全部持っている判定をどうやって書くの？

std::set を使って書きました。（僕はね）

std::setとは集合を表す連想コンテナ...難しいね。

どういうものかはちゃんと勉強してほしいけど、ひとまず std::set を使うと、ある数を持ってるか持ってないかを簡単に判別できます。これを使って実装すると以下の通り

// 先に以下をして i番目の商品のもつ機能を用意しておく
kind[i].insert(x);

//以下をさっきの条件判定のところに埋める
bool f=true;     //この下に書く想定
// i 番目の商品が持つ機能を１つずつ x に入れ込む
// for(int i=0; i<S.size();i++) S[i] なんちゃらー みたいな処理を書いている。
// 詳しくは範囲forで検索
for(auto x : kind[i]){
  // j 番目の商品の持つ機能の中で、xの数が0個だったら
  // つまり、xと言う機能を持ってなかったら
  if(kind[j].count(x)==0){ 
    f=false;  // fはfalseとなり条件をみたさない
  }
}

実装例

入力を含めた例をおいておく。

// 入力
int N,M;
cin>>N>>M;
vector<int> P(N);
vector<set<int>> kind(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;
    kind[i].insert(F);
  }
}
// 入力終わり
for(int i = 0; i < N; i++){   //  商品Aは i 番目、
  for(int j=0; j < N ; j++){  // 商品Bは j 番目とする
    if(i==j)continue;         //AとBが同じ商品のときはスキップ
    if(P[i] < P[j])continue;  //Bの方が値段が高いときはスキップ
    bool f=true;
    for(auto x : kind[i]){
      if(kind[j].count(x)==0){ 
        f=false;  // fはfalseとなり条件をみたさない
      }
    }
    if(!f)continue; // 条件満たさないので次へ
    if(P[i]>P[j] || kind[j].size()>kind[i].size() ){
      cout<<"Yes"<<endl;
      return 0; //見つかったのでプログラムをここで終える
    }
  }
}
cout<<"No"<<endl; //見つからなかったときだけここに来る。