C. Nastya and Strange Generator (Codeforces Round #637 Div. 2)

問題

https://codeforces.com/contest/1341/problem/C

問題概要

幅nの区画が横一列に並んでいて、左から順に1, 2, 3, ..., nである。

各区画に改めて別の番号を1から順に振っていく。その番号を振る際のルールは以下の通り。

• 各区画について、自分を含めて自分より右側にあって、まだ番号が振られていない区画のうち最も左にあるものの元の番号をリストに入れる
• リストの中の最瀕値である区画に新しい番号を振る
  • 最瀕値が複数ある場合、その中で任意に選択可能

（よくわからない場合は、問題のNoteを参照してください）

さて、振り直した後の番号（順列）が与えられるので、上記のルールで構築可能かどうか答えよ。

考察

これは実際に試してみればわかるのですが、最初は1を任意の場所に入れることができます。しかし、2は1の右隣にしか入れられず、3は2の右隣にしか入れられず、というのを右端に来るまで繰り返すことになります。右端まで到達すると、次の数字は任意の場所に入れることができますが、その次はまた右隣、というのを繰り返します。

結局、構築可能な順列は、ある項から右隣を見た時、一つ増加しているか、あるいは減少しているかのいずれかでなければなりません。つまり、いずれかの項の右隣が2以上増加している場合、構築不可能となります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        bool ok = true;
        for (int i = 0; i < n - 1; i++){
            if (a[i] + 1 < a[i + 1]) {
                ok = false;
                break;
            }
        }
 
        cout << (ok ? "Yes" : "No") << endl;
    }
}