ABC372 D問題の解説（Python）

はじめに

この記事では、ABC372のD問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC372　D – Buildings

問題

問題

ビル 1, 2, …, N がこの順で一列に並んでいます。ビル $i$ の高さは $H_i$ です。

各 $i$ について、次を満たす整数 $j(i<j\leqq N)$  の個数を求める問題です。

• ビル $i$ とビル $j$ の間にビル $j$ より高いビルが存在しない

制約

• $1\leqq N\leqq 2\times {10}^5$
• $1\leqq H_i\leqq N$
• $H_i\ne H_j (i\ne j)$

思考の筋道

この問題はビルを右方向に眺めたときにどのビルが見えるかを考える問題です。ビル1からではなく、ビルNから逆順に調べるとよいことに気づくのが第一歩です。例をもとに、後ろのビルから考えてみましょう。

このように具体例でシミュレーションをしてみることが非常に大切ですね。

さて、ビルiからいくつビルが見えるかは、ビルi+1からいくつビルが見えるかに比べて、次の差があります。

1. ビルi+1があることにより見えなくなったビルを除かなければならない
   （ビルi+1より低いビルを除けばOK）
2. ビルi+1を見えるビルに追加しなければならない
   （右隣のビルは必ず見えるため）

これらを処理するためにデータ構造としてスタックを用いましょう。

ビルiから見えるビルの個数を調べるためにビルi+1を調べているところが、一つずれていてややこしいですね。

コード

N = int(input())
H = list(map(int, input().split()))

ans = [0]
stack = []

for i in range(N - 2, -1, -1):
    while stack and H[i + 1] > stack[-1]:
        stack.pop()
    stack.append(H[i + 1])
    ans.append(len(stack))

ans = ans[::-1]
print(*ans)

以上、ABC372のD問題の解説でした！

では、またね。

リンク