ABC310 B問題別解

問題
B - Strictly Superior

本番で提出したABC310のB問題の解き方が公式解答と少し異なっていたようなので書いておきます。以下、提出コードです。

abc310_c.cpp

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> p(n);
	vector<int> c(n);
	vector<vector<int>> f;
	for (int i = 0; i < n; i++) {
		cin >> p[i] >> c[i];
		vector<int> f_;
		for (int j = 0; j < c[i]; j++) {
			int a; cin >> a;
			f_.push_back(a);
		}
		sort(f_.begin(), f_.end());
		f.push_back(f_);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)continue;
			if (p[i] >= p[j]) {
				vector<int> vec;
				set_intersection(f[i].begin(), f[i].end(), f[j].begin(), f[j].end(), back_inserter(vec));
				if (vec == f[i]) {
					if (p[i] > p[j] || f[j].size() > vec.size()) {
						cout << "Yes";
						return 0;
					}
				}
			}
		}
	}
	cout << "No";
	return 0;
}

問題文は割愛するので適宜参照してください。

私の実装では、2重ループで各組み合わせに対して以下の条件を満たすかどうかを判定しています。

・P[i]>=P[j]である。
・j番目の製品はi番目の製品が持つ機能をすべてもつ。
・P[i]>P[j]であるか、j番目の製品はi番目の製品にない機能を1つ以上もつ。

この条件をif文で愚直に判定を行っています。3つのif文でtrueとなるときYesを出力してreturn 0;としています。

1つ目の条件について、式通りに実装しています。

2つ目の条件について、「j番目の製品はi番目の製品が持つ機能をすべてもつ。」=「j番目のvectorとi番目のvectorの積集合がi番目のvectorと一致する」と解釈しました。

その積集合は、set_intersection(f[i].begin(), f[i].end(), f[j].begin(), f[j].end(), back_inserter(vec));でvecに格納されています。
この関数を実行するためには、対象のvectorがsort済みである必要があるため、fに各vectorを挿入する時点でsort(f_.begin(), f_.end());という処理を行っています。
こちらを参考にしました。

3つ目の条件について、P[i]>P[j]の判定はそのまま実装します。「j番目の製品はi番目の製品にない機能を1つ以上もつ」の部分について、これは「j番目のvectorがi番目のvector(あるいは積集合vec)のサイズより大きければいい」という解釈と等しいです。
すでに2番目の条件をクリアしている前提であるため、単純に各vectorの持つ整数の数を比較すれば適切な判定ができます。