とても教育的な Greedy かもしれない！

問題概要

長さ $N$ の正の整数からなる数列 $a_{1}, a_{2}, \dots, a_{N}$ が与えられる。この数列からいくつかの値を取り除くことで、数列が $1, 2, 3, \dots$ となるようにしたい。

取り除くべき個数の最小値を求めよ。どのように取り除いても $1, 2, \dots$ の形にできないときは -1 を出力せよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

たとえば 2, 4, 1, 3, 2, 5, 3, 4, 6, 5, 7 の場合は、こんな感じ

「残す数列」の先頭は 1 でなければならない。よって、最初の「2, 4」は削除しなければならない
その次の 1 は残す
「残す数列」の「1 」の次は「2」でなければならないので、「3」は削除しなければならない
その次の 2 は残す
...

と繰り返すと

2 4 1 3 2 5 3 4 6 5 7
    o   o   o o   o

という感じに「1, 2, 3, 4, 5」を残して、残りすべてを削除する方法が考えられる。なお、「取り除く個数を最小化する」というのは、残す数列「1, 2, 3, ...」の個数を最大化したいということでもある。つまり、

1, 2, 3, ...

を選んでいって、どこまで進めるかを考える問題ともいえる。そして、上のような方法は実は最適になっている。そのことを簡単に考えてみる。

最適性 (念のため)

まず、数列 $a_{1}, a_{2}, \dots, a_{N}$ の中から、取り除いてできる数列の先頭の「1」を選ばなければならない。もし $a_{1}, a_{2}, \dots, a_{N}$ の中に 1 が存在しなかったら、その時点で「-1」を出力して終了する。

数列 $a_{1}, a_{2}, \dots, a_{N}$ に複数個の「1」があったとき、果たしてどの 1 を「先頭の 1」にするべきだろうか？

少し考えてみると、数列 $a_{1}, a_{2}, \dots, a_{N}$ に登場する 1 のうち、最も左のものを選べば良い (それ以外を選ぶことには何のメリットもないため)。

そしたら、その「1」の前にあるやつはすべて取り除いてしまい、残りの中から今度は「2」を選ぶ。これも同様に、一番左にある「2」を選べばよい。以下同様。

まとめ

数列 $a_{1}, a_{2}, \dots, a_{N}$ を左から順番に見ていって

$1$ を見つけたら採用
その後 $2$ を見つけたら採用
その後 $3$ を見つけたら採用
...

を繰り返せばよい。「1」さえ見つけられなかったら -1 を出力する。計算量は $O(N)$ となる。

#include <iostream>
#include <vector>
using namespace std;

long long solve(int N, const vector<int> &a) {
    int iter = 1;
    for (int i = 0; i < N; ++i) {
        if (a[i] == iter) ++iter;
    }

    if (iter == 1) return -1;
    else return N - (iter - 1);
}

int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    cout << solve(N, a) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 148 D - Brick Break (5Q, 灰色, 400 点)

問題概要

制約

考えたこと

最適性 (念のため)

まとめ