概要

この問題は、一列に並んだ \(N\) 棟のビルからちょうど1棟を取り壊したときに、西側（左側）から見えるビルの数を最大化する問題です。

素朴に「取り壊すビルを全探索し、その都度見えるビルを数える」という方法では、1回のシミュレーションに \(O(N)\)、全体で \(O(N^2)\) の時間がかかってしまい、 \(N \le 2 \times 10^5\) の制約下では実行時間制限に間に合いません（TLEとなります）。

そこで、各ビルを取り壊したときに、見えるビルの数がどのように変化するかを効率的に計算することで、全体で \(O(N \log N)\) の時間計算量で解くことができます。

---

考察

1. ビルが見える条件の整理

ビル \(i\) が高橋君から見える条件は、「ビル \(i\) より左側（\(1\) から \(i-1\) まで）に、高さが \(H_i\) 以上のビルが1つも存在しないこと」です。

ここで、ビル \(i\) の左側にある「高さが \(H_i\) 以上のビル」の個数を \(C_i\) と定義します。 - \(C_i = 0\) のとき：ビル \(i\) はもともと見えています。 - \(C_i \ge 1\) のとき：ビル \(i\) は手前のビルに遮られて見えません。

2. ビル \(k\) を取り壊したときの影響

ビル \(k\) を取り壊したとき、全体の「見えるビルの数」は以下のように変化します。

1. ビル \(k\) 自身の影響

   • ビル \(k\) がもともと見えていた場合（\(C_k = 0\)）、取り壊すことで見えるビルの数が \(1\) 減少します。
   • もともと見えていなかった場合（\(C_k \ge 1\)）、取り壊してもこの点での減少はありません。

2. 他のビルへの影響

   • もともと見えていなかったビル \(i\) のうち、「ビル \(k\) だけに遮られていたビル」は、ビル \(k\) が消えることで新たに見えるようになります。
   • 「ビル \(k\) だけに遮られていた」とは、すなわち \(C_i = 1\) であり、かつその遮っている唯一のビルが \(k\) である状態を指します。
   • \(C_i \ge 2\) のビルは、ビル \(k\) を取り壊しても依然として別のビルに遮られるため、見えるようにはなりません。

したがって、もともと見えているビルの総数を \(V\) とすると、ビル \(k\) を取り壊した後の見えるビルの数は次のように表せます。

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

これをすべての \(k\) (\(1 \le k \le N\)) について高速に計算できれば、その最大値が答えになります。

---

アルゴリズム

各ビル \(i\) について、\(C_i\)（自分より左にあり、自分以上の高さを持つビルの数）を効率よく求めるために、フェニック木（Binary Indexed Tree, BIT）と座標圧縮を利用します。

ステップ 1: 座標圧縮

ビルの高さ \(H_i\) は最大で \(10^9\) と非常に大きいため、そのままでは BIT のインデックスとして使えません。 そこで、出現する高さの種類数（高々 \(N\) 種類）に注目し、高さを \(1\) から \(U\) (\(U \le N\)) までの整数に変換（座標圧縮）します。

ステップ 2: 左から順に走査し、遮るビルを特定する

左から順にビル \(i\) (\(0\) から \(N-1\)) を見ていきながら、以下の処理を行います。

1. 自分以上の高さのビルの数 \(C_i\) の計算

   • これまでに処理した（＝自分より左にある）ビルのうち、高さが \(H_i\) 未満のものの個数を BIT を使って求めます。これを less とします。
   • 自分より左にあるビルの総数は \(i\) 個なので、自分以上の高さのビルの数 \(C_i\) は \(C_i = i - \text{less}\) と求まります。

2. 遮っているビルの特定

   • これまでに現れたビルの高さの最大値を max_val、そのビルの番号を max_idx とします。
   • もし \(C_i = 1\) であれば、ビル \(i\) を遮っている唯一のビルは、これまでの最大値を持つビル max_idx です。したがって、add_count[max_idx] を \(1\) 増やします。
   • その後、現在のビル \(i\) の高さが max_val を更新するなら、max_val と max_idx を更新します。

3. BITの更新

   • 現在のビルの高さを BIT に追加します。

ステップ 3: 答えの集計

もともと見えているビルの総数 \(V\)（\(C_i = 0\) となる \(i\) の個数）を求めます。 各ビル \(k\) (\(1 \le k \le N\)) について、取り壊したときの値を計算し、その最大値を出力します。

---

計算量

• 時間計算量: \(O(N \log N)\)

  • 座標圧縮のためのソートに \(O(N \log N)\) かかります。
  • 各ビルに対する BIT のクエリと更新に \(O(\log N)\) かかるため、走査全体で \(O(N \log N)\) となります。
  • 最後の集計は \(O(N)\) です。
  • 全体として \(O(N \log N)\) となり、 \(N = 2 \times 10^5\) でも \(0.2\) 秒程度で高速に動作します。

• 空間計算量: \(O(N)\)

  • 座標圧縮用のマップ、BIT、および各ビルの情報を格納する配列（C, add_count など）で \(O(N)\) のメモリを使用します。

---

実装のポイント

• 1-indexed と 0-indexed の切り替え

  • BIT の操作やビルの番号（1から \(N\)）は 1-indexed で扱うとバグを減らしやすいです。実装コードでも、max_idx や add_count のキーとして 1-indexed のビル番号が使われています。

• \(C_i = 1\) のときの遮蔽ビルの特定

  • 左側にある「自分以上の高さのビル」がちょうど1つのとき、そのビルは必ず「これまでに現れた最大のビル」になります。この性質を利用することで、複雑なデータ構造を使わずに、単に変数を1つ保持するだけで遮蔽ビルを特定できます。

    ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    H = [int(x) for x in data[1 : N + 1]]

    # 座標圧縮
    unique_H = sorted(list(set(H)))
    h_to_compressed = {val: i + 1 for i, val in enumerate(unique_H)}
    compressed_H = [h_to_compressed[x] for x in H]

    U = len(unique_H)
    bit = [0] * (U + 1)

    def add(idx, val):
        while idx <= U:
            bit[idx] += val
            idx += idx & -idx

    def query(idx):
        s = 0
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx
        return s

    C = [0] * N
    add_count = [0] * (N + 1)

    max_val = 0
    max_idx = -1

    for i in range(N):
        h = compressed_H[i]
        less = query(h - 1)
        c = i - less
        C[i] = c

        if c == 1:
            add_count[max_idx] += 1

        if h > max_val:
            max_val = h
            max_idx = i + 1

        add(h, 1)

    V = sum(1 for c in C if c == 0)

    ans = 0
    for k in range(1, N + 1):
        is_visible = 1 if C[k - 1] == 0 else 0
        val = V - is_visible + add_count[k]
        if val > ans:
            ans = val

    print(ans)


if __name__ == "__main__":
    solve()

---

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