【要約】AtCoder Beginer Contest 454 参加記録と解答例（A~D問題） [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
文字列の置換ルールに基づき、特定のパターンを正規化して一致判定を行う際、単純な配列スライスを用いた置換操作では、各ステップで配列の再生成が発生し、計算量が $O(N^2)$ に膨れ上がる。これにより、大規模な入力データに対して実行時間制限（TLE）に抵触するという課題がある。
// Approach
文字列の正規化において、スタック構造を採用。パターン $(xx)$ を検出した際、配列全体をスライスで再構築するのではなく、スタックの `pop` および `append` 操作を用いることで、各置換の計算量を $O(1)$ に抑えるアプローチをとった。これにより、全体の計算量を $O(N)$ に抑え込み、効率的な判定を実現した。
// Result
5段階の試行錯誤を経て、論理的な誤り（WA）と計算量不足（TLE）を共に解消し、最終的にAC（正解）を獲得した。文字列の正規化におけるスタック操作の重要性と、Pythonにおけるリスト操作の計算量特性を実証した。
Senior Engineer Insight
> 本記事の価値は、単なる正解コードの提示ではなく、TLEに直面した際の「計算量のボトルネック」の特定プロセスにある。問題Dで見られた、スライスによる配列の再代入が $O(N)$ のコストを要し、全体で $O(N^2)$ に陥るミスは、大規模なデータストリームを扱う実務においても極めて致命的だ。スタックの `pop` と `append` を用いて $O(1)$ に抑えるという、データ構造の特性を理解した上での最適化は、低レイテンシが求められるシステム開発における基本にして極意である。実装の「正しさ」だけでなく「効率性」を常に意識する重要性を再認識させる内容だ。