TechFUL: Building Destruction

TechFUL TechFUL: 上級

問題概要

N 個のビルが左右一列に並んでいる．

i \; (1 \leq i \leq N) 番目のビルは h_{i} 個のブロックから構成されている．

Tech ちゃんは火力が x の爆弾でビルのブロックを破壊しようとしている．

破壊の方法は N 通りあり、 i 番目の破壊の仕方は次の通り．

  • 位置 j \; (i \leq j \leq N) のビルに j - i + 1 個の爆弾を置き、 j 番目のビルのブロックを x * (j - i + 1) 個破壊する．

ただし、破壊後のビルのブロックの個数が 0 個以下となるような破壊の仕方は認められないものとする．

このとき、Tech ちゃんの報酬は x * (破壊の仕方の数) である．

報酬の最大値を求めよ．

問題のリンク

制約

  • 1 \leq N \leq 10^{5}

  • 1 \leq h_{i} \leq 10^{9}

解法

まず、結論をいうと h_{N} - 1 が答えである．

以下に正当性を示す．

火力 x の爆弾で、 i 番目の破壊の仕方が認められるとする．

このとき、 h_{i} - x > 0, h_{i+1} - 2x > 0, \ldots, h_{N} - (N-i+1)x > 0が成り立つ．

h_{i+1} - x > 0, \ldots, h_{N} - (N-i)x > 0 が成り立つため i+1 番目の破壊の仕方も認められる．

同様に、 i+2, \ldots, N 番目の破壊の仕方も認められる．

i-1 番目の破壊の仕方が認められず、 i 番目の破壊の仕方が認められるとき、報酬は (N - i + 1)x である．

i 番目の破壊の仕方だと、 N 番目のビルの残りのブロックは h_{N} - (N - i + 1)x となる．

i 番目の破壊の仕方が認められるには、最低でも h_{N} - (N - i + 1)x \geq 1 を満たす必要がある．

よって、 (N - i + 1)x \leq h_{N} - 1 となり、報酬の上界が h_{N} - 1 と分かる．

x = h_{N}-1 のとき、 N 番目の破壊の仕方のみ認められる．

このとき、報酬は上界 h_{N} - 1 を達成するため、報酬の最大値は h_{N} - 1 となる．

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

int main() {
    int N;
    cin >> N;
    vector<int> h(N);
    for (int i = 0; i < N; ++i) cin >> h[i];
    cout << h[N - 1] - 1 << endl;
}