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

問題

概要

下記の件数を高速に求める問題

既存投稿一覧ページへのリンク

一覧ページ

Before

AtCoder Beginner Contest 372_C 問題

Next

AtCoder Beginner Contest 372_E 問題

その他・記事まとめ

Unity関連

解法手順1

問題のポイント

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

---

Step 1: データ構造の準備

from collections import deque

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

動作原理

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

---

Step 2: メイン処理（右から左へ走査）

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: 結果の反転処理

print(*reversed(answer))

理由

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

---

アルゴリズムの核心

キーとなる考え方

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

計算量

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

ACコード1(loggerをコメントアウトしないとTLE)

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の解法だけど、正直思いつく自信がないので、他の解法を探してみるか。

トレース用題材

円周率の並びの場合