zuka
ABCをコツコツ解いていきます。
本記事は,管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために,積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や,なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest(通称ABC)を解いていくものです。今回はABC176-C「Step」です。
ポイント
Atcoderでよく見かける問題ですね。左から全探索していき,各要素に対して「最大値」と「最大値からの差」を保持していくという問題です。実装もシンプルなため,スピード勝負の問題でした。私は最初の配列の宣言でサイズを小さく指定してしまい,見事2回REしました。
おさえるべき内容
各要素に対する「最大値」と「最大値からの差」の保持
実装
#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 N;
// しっかり条件で与えられた大きさを宣言する(自戒)
ll A[200010];
int main(){
cin >> N;
rep(i, N) cin >> A[i];
ll ans = 0;
ll max_value = A[0];
// 左から順に見ていく
rep(i, N-1){
// もし最大値より次の人が小さければ台の大きさは最大値との差になる
if (max_value > A[i+1]){
ans += max_value - A[i+1];
}
// もし次の人が最大値以上であれば最大値を更新する
else{
max_value = A[i+1];
}
}
cout << ans << endl;
}
コメント