今日勉強したことを
つらつらと
logo

abc148_dの解き方の解説 スターリンソートかよ!

2020/05/26 13:05
AtCoder Beginner Contest 148のD問題 Brick Breakを解く。

感謝の正拳突き1万回ならぬ、競プロサイトで 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);
}

© 2021 simodake