abc148_dの解き方の解説 スターリンソートかよ！
2020/05/26 13:05
感謝の正拳突き１万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。
ABC148 の D 問題 Brick Breakを解いていきます。昨日やったabc149_dに続き全探索で解けるので簡単でした。ロジックもただカウントするだけなので、もっと簡単です。
基本的な考え方
左から順番に走査していって、目的の数字以外の場合壊します。つまりカウントします。
1 から順に並ぶので、最初は 1 を探し、1 が見つかったら 2 を探し・・と順番に走査します。
入力例 2 を順番に追いかける
3 1と比較→NG、カウントする 1
1 1と比較→OK、比較する数字に1足す
4 2と比較→NG、カウントする 2
1 2と比較→NG、カウントする 3
5 2と比較→NG、カウントする 4
9 2と比較→NG、カウントする 5
2 2と比較→OK、比較する数字に1足す
6 3と比較→NG、カウントする 6
5 3と比較→NG、カウントする 7
3 4と比較→OK、比較する数字に1足す答えは 7 となります。
満足できないパターンを考える
満足できないパターンの判定方法は 2 種類あります。
- カウント == n の場合 全部のレンガを壊した場合です。
- 比較する数字 == 1 の場合 比較して OK になったレンガが 1 つもない場合です。
いわゆるスターリンソート
このアルゴリズム、実は前に書いたことがありました。2019 年夏にスターリンソートというアルゴリズムが一部で流行していました。順番に並んでいない要素を粛清することで、O(N)でソートできる画期的な速度のソートアルゴリズム（というジョーク）です。
思い出して少し笑ってしまいました。
できあがり
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll n, a;
// num : 比較する数字、cnt : レンガを壊したカウント
ll num = 1, cnt = 0;
cin >> n;
for(ll i = 0; i < n; i++) {
cin >> a;
// 満足するブロックか
if(a == num) num++;
// 壊すブロックか
else cnt++;
}
cout << fixed << (cnt == n ? -1 : cnt);
}