A - MEX Partition

この問題の核心は、配列全体のMEX（Minimum Excluded Value）を求めることに帰着します。与えられた配列 $A$ をいくつかの部分集合に分割し、そのすべての部分集合のMEXが等しくなるための条件を考えます。

$A$ のMEXを $m$ とします。$m$ は $A$ に含まれない最小の非負整数であるため、$m$ より大きい要素は各部分集合のMEX計算において無視できます。重要なのは $0$ から $m-1$ までの要素です。もし $0$ が $A$ に存在するなら、すべての部分集合は同じMEXを持つためには、必ず $0$ を含んでいなければなりません。そうでなければ、ある部分集合のMEXは $0$ になり、別の部分集合のMEXは $0$ より大きくなってしまいます。この論理は $1, 2, \ldots, m-1$ についても同様に成り立ちます。したがって、唯一可能な共通のMEXは、配列全体のMEXである $m$ です。

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

void solve() {
    int n;
    cin >> n;
    unordered_set<int> s;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        s.insert(val);
    }
    int result = 0;
    while (s.count(result)) {
        ++result;
    }
    cout << result << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B - Distinct Elements

この問題は、差分を用いて元の配列を構築する典型例です。配列 $B$ の各要素 $B[i]$ は、元の配列 $A$ の先頭から $i$ 番目までの範囲に含まれる「異なる要素の個数」として定義されています。

差分 $D[i] = B[i] - B[i-1]$ を考えると、$D[i]$ は位置 $i$ における新しい要素の寄与を表します。もし $D[i] == i+1$ であれば、これまでに登場した要素の総和がインデックスと一致するため、位置 $i$ には新しい値が現れたことになります。そうでない場合、その要素は過去のどこかで既に登場しており、その位置は $i - D[i]$ で特定できます。

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

void solve() {
    int len;
    cin >> len;
    vector<int64> prefix(len);
    for (auto &x : prefix) cin >> x;
    
    vector<int> original(len);
    original[0] = 1;
    int next_unique = 1;
    
    for (int i = 1; i < len; ++i) {
        int64 diff = prefix[i] - prefix[i-1];
        if (diff == i + 1) {
            original[i] = ++next_unique;
        } else {
            original[i] = original[i - diff];
        }
    }
    
    for (int i = 0; i < len; ++i) {
        cout << original[i] << " \n"[i + 1 == len];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C - Reverse XOR

ビット操作と列挙による解法です。整数 $x$ を2進数表現で反転させたものを $y$ とし、$x \oplus y = n$ が成り立つか判定します。

この条件が成り立つためには、$n$ の2進数表現が対称性を持っている必要があります。具体的には、$n$ のあるビット位置を中心（または2ビットの間）として、ビットパターンが対象になっていなければなりません。$n$ のあるビットが1である場合、対応する反転位置のビットも1である必要があり、その間のビットパターンが整合していれば条件を満たす $x$ が存在することになります。

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

void solve() {
    int n;
    cin >> n;
    
    for (int center = 29; center >= 0; --center) {
        int ones_count = 0;
        
        // Check symmetry around a single bit (odd length symmetry)
        if (!((n >> center) & 1)) {
            for (int offset = 1; center + offset < 60 && center - offset >= 0; ++offset) {
                int high = (n >> (center + offset)) & 1;
                int low = (n >> (center - offset)) & 1;
                if (high == low && high == 1) {
                    ones_count += 2;
                }
                if (high ^ low) break;
            }
            if (ones_count == __builtin_popcount(n)) {
                cout << "YES\n";
                return;
            }
        }
        
        // Check symmetry between two bits (even length symmetry)
        ones_count = 0;
        for (int offset = 1; center + offset < 60 && center - offset + 1 >= 0; ++offset) {
            int high = (n >> (center + offset)) & 1;
            int low = (n >> (center - offset + 1)) & 1;
            if (high == low && high == 1) {
                ones_count += 2;
            }
            if (high ^ low) break;
        }
        if (ones_count == __builtin_popcount(n)) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D - MAD Interactive Problem

インタラクティブな問題であり、効率的な質問戦略が求められます。最大 $2n$ 回の質問で配列の特定を行います。

まず、基準となるインデックス（例えば1）を用いて、他のインデックスの値との関係を調べます。これにより、いくつかの要素の値を特定しながら、値が確定していないインデックスの集合を管理します。ある程度の数（$n$個）の値が確定したら、その確定したインデックスの集合をクエリのベースとして使用し、残りの未確定のインデックスに対して質問を行うことで、配列全体の値を特定できます。

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

void solve() {
    int n;
    cin >> n;
    
    vector<int> answer(2 * n);
    
    auto query = [](const vector<int>& indices) -> int {
        cout << "? " << indices.size();
        for (int idx : indices) cout << " " << idx;
        cout << endl;
        int res;
        cin >> res;
        return res;
    };
    
    auto submit = [&]() {
        cout << "!";
        for (int x : answer) cout << " " << x;
        cout << endl;
    };
    
    vector<int> known_indices;
    known_indices.push_back(1);
    vector<int> pending_indices;
    
    // First phase: Identify n elements
    for (int i = 1; i < 2 * n; ++i) {
        known_indices.push_back(i + 1);
        int res = query(known_indices);
        if (res) {
            answer[i] = res;
            known_indices.pop_back();
            if (known_indices.size() == 1) {
                answer[known_indices.back() - 1] = res;
                known_indices.pop_back();
            } else {
                pending_indices.push_back(i + 1);
            }
        }
    }
    
    // Second phase: Resolve remaining indices using known set
    for (int idx : known_indices) {
        pending_indices.push_back(idx);
        int res = query(pending_indices);
        answer[idx - 1] = res;
        pending_indices.pop_back();
    }
    
    submit();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E - Rectangles

グリッド上の長方形の面積を最小化する問題です。全探索を行うと計算量が爆発するため、行列の転置を用いて計算量を $O(nm\min(n,m))$ に抑える工夫が必要です。

まず、行数が列数より多い場合、計算量を削減するために行列を転置します。その後、上側の行 $u$ と下側の行 $d$ をペアとして全探索します。各行 $u, d$ において、両方の行で値が $1$ である列をチェックし、その間の距離を用いて長方形の面積を計算します。ある行 $d$ における各列の最小面積を求めた後、下側の行から上側の行へ向かって最小値を伝播（Suffix Min）させることで、各セルから始まる最小の長方形の面積を効率的に更新できます。

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

void solve() {
    int rows, cols;
    cin >> rows >> cols;
    vector<vector<int>> grid(rows, vector<int>(cols));
    
    for (int i = 0; i < rows; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < cols; ++j) {
            grid[i][j] = s[j] - '0';
        }
    }
    
    // Transpose if rows > cols to optimize complexity
    bool transposed = false;
    if (rows > cols) {
        transposed = true;
        vector<vector<int>> temp(cols, vector<int>(rows));
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < cols; ++j)
                temp[j][i] = grid[i][j];
        grid = move(temp);
        swap(rows, cols);
    }
    
    const int INF = 1e9;
    vector<vector<int>> result(rows, vector<int>(cols, INF));
    
    for (int u = 0; u < rows; ++u) {
        for (int d = u + 1; d < rows; ++d) {
            int prev_one = -1;
            for (int c = 0; c < cols; ++c) {
                if (grid[u][c] && grid[d][c]) {
                    if (prev_one != -1) {
                        int area = (d - u + 1) * (c - prev_one + 1);
                        for (int k = prev_one; k <= c; ++k) {
                            result[d][k] = min(result[d][k], area);
                        }
                    }
                    prev_one = c;
                }
            }
        }
        // Propagate minimum values upwards
        for (int r = rows - 2; r >= u; --r) {
            for (int c = 0; c < cols; ++c) {
                result[r][c] = min(result[r][c], result[r + 1][c]);
            }
        }
    }
    
    // Restore original dimensions if transposed
    if (transposed) {
        vector<vector<int>> temp(cols, vector<int>(rows));
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < cols; ++j)
                temp[j][i] = result[i][j];
        result = move(temp);
        swap(rows, cols);
    }
    
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (result[i][j] == INF) result[i][j] = 0;
            cout << result[i][j] << " \n"[j + 1 == cols];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}