結果
| 問題 |
No.1963 Subset Mex
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:25:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,514 bytes |
| コンパイル時間 | 1,465 ms |
| コンパイル使用メモリ | 108,572 KB |
| 実行使用メモリ | 21,796 KB |
| 最終ジャッジ日時 | 2025-05-14 13:26:49 |
| 合計ジャッジ時間 | 9,284 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 2 TLE * 1 -- * 23 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
// Global limit for values, determined after reading N and initial S_i
int V_LIMIT_EFFECTIVE;
// Function to calculate MEX of a multiset represented by a frequency map
int calculate_mex(const std::map<int, int>& selection_counts) {
// "selection_counts" represents the chosen subset C, which must be non-empty.
// Problem statement guarantees C is non-empty.
int mex = 0;
while (true) {
if (selection_counts.count(mex)) {
mex++;
} else {
break;
}
}
return mex;
}
// Converts frequency map to counts vector
std::vector<int> to_counts_vector(const std::map<int, int>& s_map) {
std::vector<int> counts(V_LIMIT_EFFECTIVE + 1, 0);
for (auto const& [val, count] : s_map) {
if (val >= 0 && val <= V_LIMIT_EFFECTIVE) { // Defensive check for val range
counts[val] = count;
}
// Values outside this range should not occur based on problem logic
}
return counts;
}
// Converts counts vector to frequency map
std::map<int, int> to_map(const std::vector<int>& counts_vec) {
std::map<int, int> s_map;
for (int i = 0; i <= V_LIMIT_EFFECTIVE; ++i) {
if (counts_vec[i] > 0) {
s_map[i] = counts_vec[i];
}
}
return s_map;
}
// Stores distinct elements and their counts from current S for easier iteration in DFS
struct DistinctElementInfo {
int value;
int count_in_s; // Count of this value in the current multiset S
};
std::vector<DistinctElementInfo> distinct_elements_in_current_s;
// For BFS
std::set<std::vector<int>> visited_states_global;
std::queue<std::vector<int>> q_global;
// DFS function to generate subsets C
// k_distinct_idx: current index in distinct_elements_in_current_s
// current_selection_map: counts for subset C being built
// s_minus_selection_map: counts for S - C being built
void generate_subsets_dfs(
int k_distinct_idx,
std::map<int, int>& current_selection_map,
std::map<int, int>& s_minus_selection_map) {
if (k_distinct_idx == distinct_elements_in_current_s.size()) {
// Base case: a subset C (current_selection_map) and S-C (s_minus_selection_map) are formed
if (current_selection_map.empty()) { // Must select at least one element for C
return;
}
int mex_val = calculate_mex(current_selection_map);
std::map<int, int> next_s_map = s_minus_selection_map;
if (mex_val >=0 && mex_val <= V_LIMIT_EFFECTIVE) { // Add mex_val if it's within tracked range
next_s_map[mex_val]++;
}
// If mex_val > V_LIMIT_EFFECTIVE, it implies logic error or V_LIMIT_EFFECTIVE too small
// Based on analysis, mex_val should be <= N_initial <= V_LIMIT_EFFECTIVE.
std::vector<int> next_s_counts_vec = to_counts_vector(next_s_map);
if (visited_states_global.find(next_s_counts_vec) == visited_states_global.end()) {
visited_states_global.insert(next_s_counts_vec);
q_global.push(next_s_counts_vec);
}
return;
}
const auto& elem_info = distinct_elements_in_current_s[k_distinct_idx];
int val = elem_info.value;
int count_in_s = elem_info.count_in_s;
// Iterate on how many instances of 'val' are put into C
for (int count_for_selection = 0; count_for_selection <= count_in_s; ++count_for_selection) {
int count_for_s_minus_selection = count_in_s - count_for_selection;
if (count_for_selection > 0) {
current_selection_map[val] = count_for_selection;
}
if (count_for_s_minus_selection > 0) {
s_minus_selection_map[val] = count_for_s_minus_selection;
}
generate_subsets_dfs(k_distinct_idx + 1, current_selection_map, s_minus_selection_map);
// Backtrack: remove val from current_selection_map and s_minus_selection_map
if (count_for_selection > 0) {
current_selection_map.erase(val);
}
if (count_for_s_minus_selection > 0) {
s_minus_selection_map.erase(val);
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N_initial;
std::cin >> N_initial;
std::map<int, int> initial_s_map;
int max_s_i_initial = 0;
for (int i = 0; i < N_initial; ++i) {
int s_val;
std::cin >> s_val;
initial_s_map[s_val]++;
if (s_val > max_s_i_initial) {
max_s_i_initial = s_val;
}
}
V_LIMIT_EFFECTIVE = std::max(N_initial, max_s_i_initial);
// Ensure V_LIMIT_EFFECTIVE handles small N or S_i, e.g. N=1, S={0} -> V_LIMIT_EFFECTIVE=1.
// mex({0}) is 1. Max value could be 1. Counts vector size V_LIMIT_EFFECTIVE+1 is fine.
std::vector<int> initial_counts_vec = to_counts_vector(initial_s_map);
q_global.push(initial_counts_vec);
visited_states_global.insert(initial_counts_vec);
while (!q_global.empty()) {
std::vector<int> current_s_counts_vec = q_global.front();
q_global.pop();
std::map<int, int> current_s_map = to_map(current_s_counts_vec);
distinct_elements_in_current_s.clear();
for (auto const& [val, count] : current_s_map) {
distinct_elements_in_current_s.push_back({val, count});
}
// If S is empty (no distinct elements), skip. (S cannot be empty by problem logic)
if (current_s_map.empty() && !distinct_elements_in_current_s.empty()){
// This means distinct_elements_in_current_s was not cleared or current_s_map logic error.
// This should not happen.
}
if (distinct_elements_in_current_s.empty() && !current_s_map.empty()){
// This implies current_s_map has elements but distinct_elements_in_current_s is empty.
// This should not happen.
}
// The only case to check is if current_s_map is truly empty.
// But as size is at least 1, this state means something like {0:0} which is not possible.
std::map<int, int> temp_selection_map;
std::map<int, int> temp_s_minus_selection_map;
generate_subsets_dfs(0, temp_selection_map, temp_s_minus_selection_map);
}
std::cout << visited_states_global.size() % 998244353 << std::endl;
// The problem asks for count modulo 998244353. Size of set itself is the count.
return 0;
}