[AtCoder] ABC 194 E – Mex Min
問題
方針
セットとマップによる値の管理
まず初めに、セットに \( 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; }
ディスカッション
ピンバック & トラックバック一覧
[…] 公式の解説はコチラ.今回もヤマカサさんのブログが非常に参考になりました. […]