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

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

AtCoder ABC 148 D - Brick Break (400 点)

とても教育的な 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;
}