【AtCoder】ABC 405 B - Not All | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: ??? / NoviSteps: 6Q

問題概要
制約
考察
実装例
コメント

問題概要

長さ $N$ の整数列 $A$ および正整数 $M$ が与えられる。「 $A$ の末尾の要素を削除する」という操作を $0$ 回以上 $N$ 回以下行うことで、以下の条件が満たされないようにしたい。

条件： $A$ には $1$ 以上 $M$ 以下の整数がすべて含まれている。

必要な操作回数の最小値を求めよ。なお、本問題の制約下において、操作を $0$ 回以上 $N$ 回以下行うことで上述の条件が満たされないようにすることが必ず可能である。

制約

$1\leq M \leq N \leq 100$
$1\leq A_i \leq M$
入力は全て整数。

考察

$A$ の中で、 $1$ から $M$ までの各数字が最初に現れる位置を記録しておき、その最右の位置まで $A$ の要素を削除し続ければよい。

具体的には、以下のようなアルゴリズムとなる。

と初期化し、以下の配列を定義する。
- $\mathrm{first\_pos}_{i} :=$ $A$ の中で、整数 $i$ が最初に現れる index (1-indexed で、初期値は $-1$ )
に対して、次を行う。
- であるとき、
  - この整数 $i$ は $A$ の中には存在しないということであり、既に操作を行う必要はない。よって、 $0$ を出力して処理を打ち切る。
- そうでないとき、 $m \leftarrow \max(m, \mathrm{first\_pos}_{i})$ と更新する。
$N - m + 1$ が求めるべき操作の最小回数である。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];

    vector<int> first_pos(M + 1, -1);
    rep(i, 0, N)
    {
        if (first_pos[A[i]] == -1)
        {
            first_pos[A[i]] = i + 1;
        }
    }

    int m = 0;
    rep(i, 1, M + 1)
    {
        if (first_pos[i] == -1)
        {
            cout << 0 << endl;
            return 0;
        }

        chmax(m, first_pos[i]);
    }

    cout << N - m + 1 << endl;

    return 0;
}