https://atcoder.jp/contests/abc148/tasks/abc148_d
解説
https://atcoder.jp/contests/abc148/submissions/9103243
400点問題にしては、なかなか難しそうな問題に見える。
何か特殊な操作をするのだろうか。
壊すレンガを最小化するのではなく、残すレンガを最大化するよう考える。
すると、1,2,3,...というのを順番になるべく長く抜き出してくる必要がある。
これは、網羅的なアルゴリズムではなく、貪欲法で解けそうだ。
具体的には、先頭から順番に近い順に1,2,3と取っていく。
なぜ、こうして取った結果が最適かであるが、
ある1を取るときに先頭に最も近い1を取る方が、それ以外を取るより後々有利になることは分かるだろう。
つまり、選択肢がいくつかあるときに、必ず有利となる選択を毎回行うと、
先頭から近い順に1,2,3,と取っていくアルゴリズムとなる。
あとは、実装を頑張るが、先頭から精査していくなかで、どこまで取ったかを記録しておけばいい。
int N, A[201010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; int cu = 1; rep(i, 0, N) if (A[i] == cu) cu++; if (cu == 1) cout << -1 << endl; else cout << N - cu + 1 << endl; }