AtCoder Beginner Contest 136 C - Build Stairs

深夜にやったから眠すぎて嘘の考察ばかりしてしまった。（言い訳）

図で書いたらうまく頭の中で整理出来たのでやはり図は大事
（それはそう）

C問を11月までに埋めたい

問題へのリンク

問題概要

1 以上の整数Nが与えられ,N個の配列が与えられる。

それぞれの数字は1減らすことも出来るし、減らさないことも出来る。

そうした時、配列は単調非減少に出来るか求めよ

制約

• 入力は全て整数である。
• $1\le N\le {10}^5$
• $1\le H_i\le {10}^9$

解法 　:　右から順に見ていく

こんな風に数字の羅列を階段として表してあげます。

以下の画像は入力例1を図にしたものです。

そうした時、単調非減少は単調増加に置き換えれるので（ホンマか？いや、まぁサンプルを見る限りそうなのでそう扱う）階段はこの形を目指したい

 

そこで右の方から見て行って右の方の値がデカければ何もせず、左のほうがデカイなら１引いてあげてさらに見てあげるというアプローチが良さげなことが分かる。

具体的にはa[i]>=a[i-1]の時、無視で

それ以外の時にはa[i-1]--をしてさらに先ほどのa[i]>=a[i-1]の比較を行う。

もしa[i]<a[i-1]ならNoを出力する。

#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;
int main(){
  int n;cin >> n;
  vector<int> a(n);
  for(auto &i:a){
    cin >> i;
  }
  for(int i=n-1;i>=0;i--){
    if(a[i]>=a[i-1]) continue;
    a[i-1]--;
    if(a[i]<a[i-1]){cout << "No" << endl;return 0;}
  }
  cout << "Yes" << endl;
}