【要約】解説通り全探索でやったのにTLEになった話 【AtCoder典型90問032 Ekiden】 [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
競技プログラマが、AtCoderの典型問題「Ekiden」を解く際に、全探索の判定ロジックが原因でTLEに直面した。
- ・制約に基づき全順列の全探索を選択したが、判定処理の計算量がボトルネックとなった。
- ・不仲なペアの判定に、リストの走査や二重ループを用いていた。
- ・N! 通りの組み合わせに対し、各ステップで不仲リストMを走査すると、計算量が膨大になる。
- ・結果として、Python（PyPy）環境でも実行時間制限を超過した。
// Approach
筆者は、判定処理の計算量を削減するために、不仲情報を集合（set）で管理する手法を採用した。
- ・不仲なペアの情報を、リストではなく集合（set）に格納する。
- ・不仲なペア (a, b) を、順序を入れ替えた (b, a) と共に集合へ追加する。
- ・走順のループ内で、隣接するペアが集合に含まれるかを O(1) で判定する。
- ・これにより、判定処理の計算量を O(M) から O(1) へと劇的に削減した。
// Result
実装を改善した結果、実行時間を大幅に短縮することに成功した。
- ・解法2（リスト走査）の4022msから、解法3（集合利用）の314msへと改善した。
- ・実行時間は約12.8分の1にまで短縮された。
- ・集合を用いることで、コードが簡潔になり、可読性も向上した。
- ・計算量の最適化が、実行時間の改善に直結することを実証した。
Senior Engineer Insight
> アルゴリズムの計算量設計において、データ構造の選択は極めて重要である。本件では、判定処理をO(M)からO(1)へ落としたことが決定打となった。大規模なシステムにおいても、高頻度で実行されるループ内での検索処理は、必ずハッシュテーブル等の高速なデータ構造を用いるべきだ。定数倍の改善が、システム全体のレイテンシに決定的な差を生む。