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

zuka

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

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

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC140-C「maximal Value」です。

ポイント

一見意味が分かりづらい問題ですが，冷静に考えれば毎回以下のように$A_{i}$を選べば良いだけです。

証明

以下では式($\ref{A_i}$)を証明していきます。まず，$A$の総和を最大化するためには，初期値として$A_{1}$には必ず$B_{1}$を入れる必要があります。なぜなら，問題文の条件

を満たすように選んだときに最大となる数が$B_{1}$だからです。同様に，$A$の末尾$A_{N}$には$B_{N-1}$が必ず入ります。

次に，$A_{2}$を考えるのですが，問題文の条件($\ref{condition}$)より，$A_{2}$には$B_{1}$以下であり，かつ$B_{2}$以下であるような数を入れる必要があります。式で書くと以下のようになります。

この中から最大となる$A_{2}$を選べば良いのですが，それは$B_{1}$と$B_{2}$のうち小さい方を選ぶことに等しいです。それはつまり，式($\ref{A_i}$)のことを指しています。あとは，帰納的に式($\ref{A_i}$)が示されます。ここまでくれば，実装は難しくはありません。

実装

#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 B[N-1];
  rep(i, N-1){
    cin >> B[i];
  }
  // 初期値
  int ans = B[0];
  // 式(1)
  rep(i, N-2){
    ans += min(B[i], B[i+1]);
  }
  // Aの最後はBの最後と等しい
  ans += B[N-2];
  cout << ans << endl;
}