概要

東西に並んだ \(N\) 棟のビルのうち、1棟だけを取り壊したときに「西側から見えるビルの数」を最大化する問題です。

考察

素朴なアプローチとその限界

取り壊すビルを1つずつ愚直に決め打ちし、その都度見えるビルを数え上げる方法が考えられます。しかし、この方法では1回のシミュレーションに \(O(N)\) かかり、全体で \(O(N^2)\) の計算量となります。制約が \(N \leq 2 \times 10^5\) であるため、実行時間制限に間に合いません（TLE）。

したがって、各ビルを取り壊したときの影響を、より効率的に（\(O(1)\) などで）計算する必要があります。

効率的なアプローチ

ビル \(k\) を取り壊した後に見えるビルの数は、以下のように表すことができます。

\[(\text{取り壊し後に見えるビルの数}) = (\text{元々見えていたビルの数}) - (\text{ビル } k \text{ が元々見えていたなら } 1, \text{ そうでないなら } 0) + (\text{ビル } k \text{ を取り壊したことで、新たに見えるようになるビルの数})\]

「元々見えていたビルの数」と「各ビルが元々見えているか」は、左から1回走査するだけで簡単に求まります。 問題は、「ビル \(k\) を取り壊したことで、新たに見えるようになるビルの数」をどう効率よく数えるかです。

あるビル \(i\) が、ビル \(k\) を取り壊すことで「新たに見えるようになる（救われる）」ための条件を考えてみましょう。ビル \(i\) より左側（西側）にあるビルの高さの最大値を \(max_1\)、2番目に大きい高さを \(max_2\) とします。

1. ビル \(i\) は元々は見えていない：すなわち \(H_i \leq max_1\) である。
2. ビル \(i\) を遮っているビルが、左側にちょうど1つしか存在しない：もし2つ以上あれば、1つを取り壊しても別のビルに遮られてしまいます。したがって、最大値 \(max_1\) を持つビルが唯一（インデックスを \(idx_1\) とする）でなければなりません。
3. その遮っているビルが、取り壊すビル \(k\) である：すなわち \(k = idx_1\) である。
4. ビル \(k\) を取り壊した後に、ビル \(i\) が見えるようになる：ビル \(k\) を取り壊すと、左側のビルの最大値は \(max_2\) に下がります。ビル \(i\) が見えるようになるためには、残ったビルよりも高くなければならないため、\(H_i > max_2\) である必要があります。

これらをまとめると、ビル \(i\) を走査している時点で、「最大値が唯一（\(idx_1 \neq -1\)）であり、かつ \(H_i > max_2\)」を満たしている場合、ビル \(idx_1\) を取り壊すことでビル \(i\) が新たに見えるようになることが分かります。

左から順にビルを走査しながら \(max_1\) や \(max_2\) を更新していくことで、各ビル \(i\) が「どのビルを取り壊せば救われるか」を \(O(1)\) で判定し、取り壊すビルごとの「救えるビルの数（gain）」をカウントしていくことができます。

---

アルゴリズム

1. 変数の定義:

   • visible_count: 初期状態で最初から見えているビルの総数。
   • is_visible[i]: ビル \(i\) が最初から見えているかどうかを表す真偽値。
   • gain[k]: ビル \(k\) を取り壊すことで、新たに見えるようになるビルの数。
   • max1: これまでに現れたビルの高さの最大値。
   • idx1: max1 を持つビルの番号（複数ある場合は \(-1\)）。
   • max2: これまでに現れたビルの高さの2番目の最大値。

2. 左からの走査 (\(i = 1\) から \(N\) まで):

   • 見えるかどうかの判定:
     • もし \(H_i > max1\) なら、ビル \(i\) は最初から見えます。visible_count を \(1\) 増やし、is_visible[i] = true とします。
     • そうでない場合、もし idx1 != -1 かつ \(H_i > max2\) なら、ビル \(idx1\) を消せばビル \(i\) が見えるようになります。よって gain[idx1] を \(1\) 増やします。
   • 状態（最大値・2番目の最大値）の更新:
     • \(H_i > max1\) のとき: \(max2 \leftarrow max1\), \(max1 \leftarrow H_i\), \(idx1 \leftarrow i\)。
     • \(H_i = max1\) のとき: 最大値が複数になるため、\(max2 \leftarrow max1\), \(idx1 \leftarrow -1\)。
     • \(H_i < max1\) のとき: \(max2 \leftarrow \max(max2, H_i)\)。

3. 最大値の計算: 各ビル \(k\) (\(1 \leq k \leq N\)) について、ビル \(k\) を取り壊したときの見えるビルの数 visible_count - (is_visible[k] ? 1 : 0) + gain[k] を計算し、その最大値を出力します。

---

計算量

• 時間計算量: \(O(N)\) ビルを左から右へ1回走査するだけで、各ステップの処理はすべて \(O(1)\) で行われます。最後の最大値を求めるループも \(O(N)\) であるため、全体で \(O(N)\) となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N)\) ビルの高さ、見えているかどうかのフラグ、および各ビルを取り壊したときの gain を記録する配列を保持するため、空間計算量は \(O(N)\) となります。

---

実装のポイント

• 最大値が複数ある場合の処理: \(H_i = max1\) となったときに、idx1 を -1 に更新することが重要です。これにより、「最大値のビルが2つ以上あるため、どちらか一方を取り壊しても、もう片方に遮られて後ろのビルは救われない」という状況を正しく表現できます。

• 高さの範囲: ビルの高さ \(H_i\) は最大で \(10^9\) になるため、比較や代入の際にオーバーフローを防ぐために適切な型（C++では long long 型など）を使用します。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> H(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }

    long long max1 = 0;
    int idx1 = -1;
    long long max2 = 0;

    int visible_count = 0;
    vector<bool> is_visible(N + 1, false);
    vector<int> gain(N + 1, 0);

    for (int i = 1; i <= N; ++i) {
        if (H[i] > max1) {
            visible_count++;
            is_visible[i] = true;
        } else {
            if (idx1 != -1 && H[i] > max2) {
                gain[idx1]++;
            }
        }

        // 状態更新
        if (H[i] > max1) {
            max2 = max1;
            max1 = H[i];
            idx1 = i;
        } else if (H[i] == max1) {
            max2 = max1;
            idx1 = -1;
        } else {
            max2 = max(max2, H[i]);
        }
    }

    int max_visible = 0;
    for (int k = 1; k <= N; ++k) {
        int current = visible_count - (is_visible[k] ? 1 : 0) + gain[k];
        max_visible = max(max_visible, current);
    }

    cout << max_visible << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。