【要約】AtCoder Beginner Contest 458 参加記録と解答例 (A～D問題) [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
競技プログラミングの参加者は、与えられた制約時間内に、各問題の計算量制約を満たすアルゴリズムを実装する必要がある。本記事で扱われる課題は以下の通りである。
- ・A・B問題：文字列の切り出しや、グリッド内の隣接マス数のカウントといった単純な走査。
- ・C問題：文字列内の特定の文字を中心とした、奇数長の連続部分文字列の総数算出。
- ・D問題：クエリごとに要素が追加される集合において、常に中央値を高速に取得する問題。
// Approach
参加者は各問題の制約に基づき、計算量を意識した解法を採用している。具体的な手法は以下の通りである。
- ・A問題：Pythonのリストスライスを利用し、先頭と末尾の $N$ 文字を効率的に除去。
- ・B問題：二重ループと方向ベクトルを用い、全マスの四方向を走査して隣接マスをカウント。
- ・C問題：文字列を走査し、「C」を発見するたびに、左右の端までの距離から部分文字列数を算出。
- ・D問題：2つの優先度付きキュー（最大ヒープと最小ヒープ）を用い、要素の大小関係を維持しながら中央値を管理。
// Result
各問題において、制約時間内に動作する適切な計算量の解法が提示されている。
- ・A〜C問題：線形時間 $O(N)$ または $O(H \times W)$ での解決。
- ・D問題：クエリ数 $Q$ に対して $O(Q \log Q)$ の計算量を実現。
Senior Engineer Insight
> D問題で用いられた「2つのヒープによる中央値管理」は、ストリームデータ処理における統計量の動的更新という観点で重要である。実務におけるリアルタイム解析では、メモリ効率やスレッドセーフな実装、数値のオーバーフロー対策が別途求められる。アルゴリズムの正当性だけでなく、エッジケースへの耐性を高める実装力が、大規模システムでは不可欠となる。