AtCoder が提供しているABC（AtCoder Beginner Contest）310 のB問題をC++とPythonで解いてみました。ABC310は、2023年7月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Strictly Superior（Difficulty : 226）
問題はリンク先をご覧ください。
複数の集合から取り出した2つの集合が包含関係にあるか調べていく問題です。AtCoder Problems による Difficulty は 226 でした。
解答案
問題が述べている「上位互換」とは次のいずれかとなります。
- 元の機能にある機能をすべて持ち、元の機能にない機能を持つ。元の価格以下となる。
- 元の機能と同じ機能を持ち、元の価格より安い。
C++ プログラム例（ABC310B）
それぞれの商品の機能は set コンテナ f[i] に格納します（17行目）。
すべての f[i] と f[j] に対して以下を確認します。
- 添え字 i と j が等しいか、p[i] < p[j] の場合は次の組を調べる（24ー26行目）。
- f[i] のすべての要素 e に対して、f[j] がそれを持っているか調べる（28ー32行目）。
- f[j] が f[i] のすべての要素を持つ場合、以下を確認する（33ー37行目）。
- 価格が安い場合は、上位互換となる。
- f[j] の機能が多ければ、上位互換となる。
計算量は、$O(N^2 M \log M)$ となります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> p(n);
vector<set<int>> f(n);
for (int i = 0; i < n; ++i) {
cin >> p[i];
int c;
cin >> c;
for (int j = 0; j < c; ++j) {
int t;
cin >> t;
f[i].insert(t);
}
}
bool result = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if ((i == j)||(p[i] < p[j])) {
continue;
}
bool temp = true;
for (auto e : f[i]) {
if (f[j].find(e) == f[j].end()) {
temp = false;
}
}
if (temp) {
if ((p[i] > p[j])||(f[i].size() < f[j].size())) {
result = true;
}
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC310B）
Python では、機能 fi,j を、リストに格納しました（8行目）。f[i] に存在するすべての要素が f[j] に含まれているか、in 演算子で判定しています（16、17行目）。
"""AtCoder Beginner Contest 310 B"""
n, m = map(int, input().split())
p = []
f = []
for i in range(n):
product = list(map(int, input().split()))
p.append(product[0])
f.append(product[2:])
result = False
for i in range(n):
for j in range(n):
if i == j or p[i] < p[j]:
continue
temp = True
for e in f[i]:
if e not in f[j]:
temp = False
if temp:
if p[i] > p[j] or len(f[i]) < len(f[j]):
result = True
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
B問題としては、実装が重めかもしれません。AtCoder 公式解説では、includes を使っていました。includes は、ITP2 で解説していましたが気が付かず、set を使って実装しました。ただし、set の実装の方が少ない知識でプログラムを書くことができると思います。
引き続き ABC の問題を紹介していきます。
