【ABC453 D】Go Straight 復習メモ：BFSの状態管理とTLE対策 | TechDistill

> Source: Zenn_Python

// Problem

単純な座標ベースのBFSでは、直前の移動方向に依存するマスの制約を扱えない。また、Pythonにおいて状態数が多い探索を行う際、`set()` によるハッシュ計算とタプル生成のオーバーヘッドが原因で、実行時間制限（TLE）に抵触するという課題がある。

// Approach

状態を「座標 $(y, x)$」と「直前の移動方向」の組み合わせとして再定義し、状態空間を拡張した。さらに、訪問済み管理を `set()` から、方向インデックスを持つ3次元配列へ変更することで、ハッシュ計算を排除し、定数倍の高速化を実現した。

// Result

状態の再定義とデータ構造の最適化により、Python環境下でも制限時間内に正解（AC）を得ることができた。経路復元には、探索時のインデックスを保持する手法を用いている。

Senior Engineer Insight

> 競技プログラミングの知見ではあるが、本質的な課題は「データ構造の選択による定数倍の差」である。実務の低レイテンシ・高スループットなシステムにおいても、ハッシュ計算のコストやメモリレイアウトの影響は無視できない。特に、状態数が膨大な場合に `set` や `dict` を多用すると、キャッシュ効率の低下やハッシュ衝突による性能劣化を招く。アルゴリズムの計算量（オーダー）だけでなく、実装レベルでの定数倍の最適化が、システムの限界性能を決定づけることを再認識させる内容である。