問題概要
次の最大値に向かうように左右への分岐を繰り返すときに、最終的な移動距離の最大化をする
問題リンク
私の解法
- 探索階層が十分に低いため、DFSで愚直しみゅれーしょん
- 「max値セグ木と逆引配列の同時使用」で区間内の最大値の添え字を高速で求める
実行速度はO(N logN logN)ぐらい。
提出リンク (C++, 60ms)
公式解法
- DFSで各頂点に訪問しみゅれーしょん
- 「単調スタック」を用いて、現在地点より左/右の「次」に大きい添え字を定数時間で求める
実行速度はO(N)くらい。
提出リンク (C++, 40ms)
感想
ただ通すだけなら、私の解法の方が、発想が簡単。
コードの簡潔さや実行速度の観点でみると、将来的には公式解法も覚えておきたいです。