【競技プログラミング】AtCoder Beginner Contest 372_D問題

# 問題
https://atcoder.jp/contests/abc372/tasks/abc372_d

## 概要
下記の件数を高速に求める問題
![2504250925.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/2f4ff668-eb46-4189-b03e-237686fa4409.png)



# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

## Before
[AtCoder Beginner Contest 372_C 問題](https://qiita.com/o_chan_t/items/7ae566ee0a510d234a80)

## Next
[AtCoder Beginner Contest 372_E 問題](https://qiita.com/o_chan_t/items/ede9ff0c9fe4b76d2396)

## その他・記事まとめ
[Unity関連](https://qiita.com/o_chan_t/items/0b5ae1e7c45f106082b8)


# 解法手順1
## 問題のポイント

ビルiから見て右側にあるビルjのうち、「jまでの間に**jより高いビルが存在しない**」条件を満たすjの個数を効率的に計算する。

---
## Step 1: データ構造の準備
```python
from collections import deque

answer =        # 各ビルの答えを格納（初期値0）
visible_count = 1  # 現在見えるビルの数
building_deque = deque()
building_deque.append(heights[-1])  # 最後のビルを追加
```

**動作原理**  
- `deque`で「見える可能性のあるビル群」を管理
- 右側のビルから順番に処理（後ろから前へ）

---

## Step 2: メイン処理（右から左へ走査）
```python
for i in reversed(range(N-1)):  # 最後から2番目のビルから開始
    answer.append(visible_count)
    
    # 現在のビルより低いビルを除去
    while building_deque and building_deque < heights[i]:
        building_deque.popleft()
        visible_count -= 1
    
    # 現在のビルをdequeの先頭に追加
    building_deque.appendleft(heights[i])
    visible_count += 1
```

**動作説明**  
1. `answer`に現在の可視数を追加
2. 現在のビル(`heights[i]`)より低いビルをdequeから除去
3. 現在のビルをdequeの先頭に追加し、可視数を更新

---

### Step 3: 結果の反転処理
```python
print(*reversed(answer))
```

**理由**  
- 右から左に処理した結果を、元の順序に戻すため反転

---

## アルゴリズムの核心

### キーとなる考え方
- **単調減少キュー**を維持することで、不要な比較を省略
- 各ビルを追加する際、自分より低いビルを全て除去 → 残ったビルは全て自分より高い

### 計算量
- 各ビルはdequeに1回追加・最大1回削除される → **O(N)** の計算量

# ACコード1(loggerをコメントアウトしないとTLE)
```python:ac.py
import logging
from collections import deque

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

def io_func():
    N = int(input())
    heights = list(map(int, input().split()))
    return N, heights

def solve(N, heights, logger):
    # 各ビルiについて、i<j≤N かつ「ビルjの間にビルjより高いビルが無い」jの個数を求める
    answer = [0]
    visible_count = 1
    building_deque = deque()
    building_deque.append(heights[-1])
    logger.debug(f"初期状態: building_deque={list(building_deque)}, answer={answer}, visible_count={visible_count}")

    for i in reversed(range(N-1)):
        answer.append(visible_count)
        logger.debug(f"ビル{i+1}の処理開始: 高さ={heights[i]}")
        while building_deque and building_deque[0] < heights[i]:
            removed_height = building_deque.popleft()
            visible_count -= 1
            logger.debug(f"  ビル{i+2}({removed_height})より低いのでdequeから除去, visible_count={visible_count}")
        building_deque.appendleft(heights[i])
        visible_count += 1
        logger.debug(f"  ビル{i+1}({heights[i]})をdeque左端に追加, building_deque={list(building_deque)}, visible_count={visible_count}, answer={answer}")

    print(*reversed(answer))

def main():
    logger = setup_logger(debug_mode=True)
    N, heights = io_func()
    solve(N, heights, logger)

if __name__ == "__main__":
    main()

```

この解き方は、公式Youtubeの解法だけど、正直思いつく自信がないので、他の解法を探してみるか。
<iframe width="560" height="315" src="https://www.youtube.com/embed/JUJ_iehtDZY?si=gpaqEndkQ0ABtelv&amp;start=2712" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>


# トレース用題材
## 円周率の並びの場合
![2504262238.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/4153903a-2029-48e4-95b3-e612b37d7ef7.png)