[AtCoder] ABC 194 E – Mex Min

2021年3月12日

問題

方針

セットとマップによる値の管理

まず初めに、セットに \( 1 \) から \( M \) までの値を入れます。次に、先頭から \( M \) 個までの \( M \) 未満の値の頻度をマップで管理します。このとき現れた値をセットから削除します。このとき、\( \rm{mex} \) の値はセットの先頭になります。このようにして全探索します。

配列による頻度の管理

まず初めに先頭から \( M \) 個までの \( A_i \) の頻度を配列 \( B \) で管理します。\( B_i = 0 \) となるような最小の \( t \) は

\[ t = \mathrm{mex} (A_1, A_2, \cdots, A_M)\]

を満たします。次に、\( t < \mathrm{mex} (A_2, A_3, \cdots, A_{M + 1})\) となるかを調べるには、

\begin{eqnarray}
B_{A_1} & \leftarrow & B_{A_1}- 1\\
B_{A_{M+1}} & \leftarrow & B_{A_{M+1}} + 1
\end{eqnarray}

と更新し、\( B_{A_{1}} = 0 \) であるとき、\( A_{1} < t\) となるかどうかを確認すれば良いです。

コード

セットとマップ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N, M;
    cin >> N >> M;
    int A[N];
    for (int i  = 0; i < N; i++) {
        cin >> A[i];
    }
    set<int> s;
    map<int, int> m;
    for (int i = 0; i <= M; i++) {
        s.insert(i);
    }
    for (int i = 0; i < M; i++) {
        if (A[i] < M) {
            m[A[i]]++;
            s.erase(A[i]);
        }
    }

    int ans = *s.begin();

    for (int i = 1; i <= N - M; i++) {
        if (A[i - 1] < M) {
            if (m[A[i - 1]] == 1) {
                m.erase(A[i - 1]);
                s.insert(A[i - 1]);
            } else {
                m[A[i - 1]]--;
            }
        }
        if (A[i + M - 1] < M) {
            m[A[i + M - 1]]++;
            s.erase(A[i + M - 1]);
        }
        ans = min(ans, *s.begin());
    }
    cout << ans << "\n";
    return 0;
}

配列

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N, M;
    cin >> N >> M;
    int A[N];
    int B[N] = {};
    for (int i  = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < M; i++) {
        B[A[i]]++;
    }
    int ans = N;
    for (int i = 0; i < N; i++) {
        if (B[i] == 0) {
            ans = i;
            break;
        }
    }
    for (int i = 0; i < N - M; i++) {
        B[A[i]]--;
        B[A[i + M]]++;
        if (B[A[i]] == 0) ans = min(ans, A[i]);
    }
    cout << ans << "\n";
    return 0;
}