seriruの技術屋ブログ

競技プログラミングやゲーム開発など技術に関することを発信します

AtCoder Beginner Contest 116 C Grand Garden

問題

atcoder.jp

問題概要

全てを  0 に初期化された数列のうち, ある区間を選んで  1 ずつ増やしていく。
この数列を数列  h と等しくするには何回操作を行う必要があるか。

考察

数列  h のうち最大の要素を  max とします。
また, 要素数 h と等しい, 全てが0で初期化された配列  t を用意します。
一回の操作では各要素を  1 しか増やせないため  0 から  max まで,  h t と比較しつつ, 操作をシミュレーションすれば良いです。

提出コード

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<ll> h(n);
  // 数列hの最大値, 最小値
  ll mmin = 1000, mmax = -1;
  rep(i,n) {
    cin >> h[i];
    mmin = min(h[i],mmin);
    mmax = max(h[i],mmax);
  }

  ll ans = mmin;
  // 数列tは最小値で初期化しておく(最小値回, 区間(0,n-1)に水をかけることは確定している)
  vector<ll> t(n,mmin);
  
  for (int i = mmin; i <= mmax; ++i) {
    // 1つ前の要素を増加させているかを判断するフラグ
    bool flag = false;
    for (int j = 0; j < n; ++j) {
      if (t[j] < h[j] and !flag) {
        // フラグが立っていなければ, 要素jが区間の左端になる
        flag = true;
        // 実際に配列tもインクリメントして操作をシミュレート
        t[j] += 1;
      } else {
        if (flag) {
          // フラグが立っていればこの1つ前の要素が区間の右端
          ans += 1;
          // フラグを折っておく
          flag = false;
        }
      }
    }
    // 右端を見た後にフラグが立っていれば, 要素n-1が区間の右端だったことがわかる
    if (flag) {
      ans += 1;
    }
  }

  cout << ans << endl;
}