ABC136 C問題 Build Stairs

atcoder.jp

問題文

左右一列に $N$ 個のマスが並んでおり、左から $i$ 番目のマスの高さは $H_i$ です。

あなたは各マスについて $1$ 度ずつ次のいずれかの操作を行います。

• マスの高さを $1$ 低くする。
• 何もしない。

操作をうまく行うことでマスの高さを左から右に向かって単調非減少にできるか求めてください。

制約

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

解法の方針

1. 左から順に見ていって、減らせるものは1減らす

   　ここで、減らせるもの＝ 左の数字より大きいもの

   　つまり、一番左の数字は必ず減らせる

2. 操作が終わったら、条件を満たしているか確認する

注意点

　最初、次のように解こうとしたが、testcase_03、04でWAが出てしまった

　誤った手順

1. 左の数－右の数＝1のとき、左の数を1減らす
2. 操作が終わったら、条件を満たしているか確認する　

　これだと、(1,2,2,2,1)のようなものが来たとき、Noを出力してしまう

　これは、左側だけ見れば成り立っているが、右から2番目の2に来た時に減らしても、それまでの2が減っておらず、合わなくなるためである

　減らせるものは減らすという貪欲法チックな思考が必要

解答例

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)
 
int main(){
  int n;
  cin>>n;
  if(n==1){
    cout<<"Yes"<<endl;
    return 0;
  } 
  vector<int> vec(n);
  rep(i,n) cin>>vec[i];
  vec[0]-=1;
  rep(i,n-1){
    if(vec[i]<vec[i+1]){
      vec[i+1]-=1;
    }
  }
  rep(i,n-1){
    if(vec[i]>vec[i+1]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

学んだこと

貪欲法的考え方は常に持っておくべき

後ろから見ると考えやすいかも