Official
B - Strictly Superior Editorial
by
B - Strictly Superior Editorial
by
MMNMM
ありえる \(i,j\) をすべて試し、\(i\) 番目の商品と \(j\) 番目の商品が条件を満たすかをチェックすることでこの問題を解くことができます。
計算量は \(O(N^2M)\) 時間です。
ソートされた列 \(A,B\) について、\(A\) に含まれていて \(B\) に含まれていない要素が存在するか判定するには、std::includes
関数を使うことができます。
それぞれの商品について、機能 \(k\ (1\leq k\leq M)\) をもつかどうかを連続する \(M\operatorname{bit}\) で管理することで、ワードサイズ \(w\) について計算量を \(O(N^2M/w)\) 時間とすることもできます。
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
// product_j が product_i の上位互換か判定する
bool is_strictly_superior(const pair<int, vector<int>> &product_i, const pair<int, vector<int>> &product_j) {
const auto&[price_i, feature_i]{product_i};
const auto&[price_j, feature_j]{product_j};
return price_i >= price_j &&
includes(feature_j.begin(), feature_j.end(), feature_i.begin(), feature_i.end()) &&
(price_i > price_j || !includes(feature_i.begin(), feature_i.end(), feature_j.begin(), feature_j.end()));
}
// products に上位互換の組があるか判定する
bool has_superior_pair(const vector<pair<int, vector<int>>> &products) {
return any_of(products.begin(), products.end(), [&products](const auto &product_i) {
return any_of(products.begin(), products.end(), [&product_i](const auto &product_j) {
return is_strictly_superior(product_i, product_j);
});
});
}
int main() {
int N, M;
cin >> N >> M;
vector<pair<int, vector<int>>> products(N);
for (auto&&[price, feature] : products) {
cin >> price;
int K;
cin >> K;
feature = vector<int>(K);
for (auto &&f : feature)
cin >> f;
}
cout << (has_superior_pair(products) ? "Yes" : "No") << endl;
return 0;
}
posted:
last update: