zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC116-C「Grand Garden」です。
ポイント
少し頭を悩ませる問題でした。問題をシンプルに捉えれば「1がある区間連続する数列（ベクトル）を何回足し合わせれば与えられた数列を生成することができるか」という問題になります。
例えば{1,2,3,4}という数列が与えられれば{1,1,1,1}，{0,1,1,1}，{0,0,1,1}，{0,0,0,1} という4つの数列（ベクトル）を足せば与えられた数列を生成でき，この4つの数列（ベクトル）を用いる場合が最小です。
この問題のポイントは「1がある区間連続する数列（ベクトル）」をどのようにして実装するかという点です。最もシンプルな方法は，全ての要素を左から順番にみていくことを「全ての要素が0になるまで」繰り返すという方法です。
左から順番にみていくときに，0の要素と出会った場合にはそこで「1がある区間連続する数列（ベクトル）」の生成をストップします。こうすることで何個「1がある区間連続する数列（ベクトル）」を足し合わせれば良いかをカウントすることができます。
おさえるべき内容
1がある区間連続する数列（ベクトル）の実装方法
実装
#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;
typedef long long ll;
int max_elem(vector<int> X){
vector<int> Y = X;
sort(Y.begin(), Y.end());
return Y[Y.size() - 1];
}
int main(){
int N;
cin >> N;
vector<int> h(N);
rep(i, N) cin >> h[i];
// 連続する1を要素とするベクトルを足した回数
int ans = 0;
// 全てが0になるまで繰り返す
while (true){
// 全てが0ということは最大値が0ということ
if (max_elem(h)==0) break;
// みている花のインデックス
int cnt = 0;
// 1が連続する区間の最初であるかどうかのフラグ
bool flag = true;
// 全ての花を見る
while (cnt < N){
// もし見ている花の高さが0であればflagをtrueにする
if (h[cnt]==0) flag=true;
// 高さが0でないとき
else{
// 連続する区間の最初であればansをインクリメント
if (flag) ans++;
// 区間の最初はすぎたのでflagはfalseにする
flag = false;
h[cnt]--;
}
cnt ++;
}
}
cout << ans << endl;
}
コメント