【競プロ精進ログ】ABC136-C

zuka

ABCをコツコツ解いていきます。

本記事は,管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために,積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や,なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

目次

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest(通称ABC)を解いていくものです。今回はABC136-C「Build Stairs」です。

ポイント

段数がそこまで多くないので全ての段数に関して非単調減少になるかどうか調べていけばOKです。非単調減少を調べるには,最高段数を保存する変数と,減少していないかを保持するboolフラグを用意すれば良いでしょう。

おさえるべき内容

 最高段数の保存変数と減少性のチェックフラグを用意する

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;

int main(){
  int N;
  cin >> N;
  int H[N];
  rep(i, N){
    cin >> H[i];
  }
  // 一番高い段数を保存する変数
  int now = 0;
  // 減少してしまった場合にfalseにするフラグ
  bool flag = true;
  // 全ての階段についてみていく
  rep(i, N-1){
    // もし段数が増加していれば続ける
    if (H[i] - H[i+1] < 1) continue;
    // もし段数が1段減少していれば今の段数を1減らす
    if (H[i] - H[i+1] == 1){
      H[i]--;
      // もし一番高い段数よりも低くなってしまえばfalseにする
      if (H[i] < now) flag=false;
      // 一番高い段数よりも低くなければ一番高い段数を更新する
      else now = H[i];
    }
    // 次の段数が2段以上低ければfalseにする
    if (H[i] - H[i+1] > 1) flag=false;
    // falseになっていればbreakしてしまう
    if (flag == false) break;
  }
  if (flag==true) cout << "Yes" << endl;
  else cout << "No" << endl;
}
よかったらシェアしてね!

コメント

コメントする

目次
閉じる