Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps
お題箱より。
問題概要
本のビルがあり、 番目のビルの高さは である。
ビル からビル へは、 かつ以下の3条件のいずれか1つを満たす場合にジャンプして移動することができる。
- :ビル は隣り合っている。
- :間にあるビルが全て、ビル の両方より低い。
- :間にあるビルが全て、ビル の両方より高い。
ビル からビル に到達するために必要なジャンプ回数の最小値を求めよ。
制約
解法
「間にあるビルが全て、ビル の両方より低い」という状況を図示します。
ビルの組 が条件を満たしていて、図のように のほうが低い場合、もう一方のビル はビル から見て「自身より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」になっているという性質があります。そうでないもの、例えば や については条件を満たしません。
もしビル のほうが低ければ、逆にビル が「自身より左側にあり、自身以上の高さを持つビルのうち、最も近いもの」となります。ビル の高さが等しい場合は左右どちらから見た性質も成り立ちます。
そしてこの性質が成り立つことが、 「間にあるビルが全て、ビル の両方より低い」という条件を満たすことの必要十分条件になっています。
よってこれらの性質を満たすビルの組 を探すことにします。逆パターンの「間にあるビルが全て、ビル の両方より高い」という条件も含めると、結局全てのビル について
- ビル より右側にあり、自身以上の高さを持つビルのうち、最も近いもの
- ビル より左側にあり、自身以上の高さを持つビルのうち、最も近いもの
- ビル より右側にあり、自身以下の高さを持つビルのうち、最も近いもの
- ビル より左側にあり、自身以下の高さを持つビルのうち、最も近いもの
を探せば良いことになります。これらを全て求めると「隣り合っているビルの組」も自動的に含まれるので、これでジャンプ可能なビルの組を網羅できます。
4パターン全てほぼ同様に解くことができるので、一例として「ビル より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」の求め方を考えます。これはスタックを使って解くと効率的です。
ビルを左から順番に見ていきます。ビル を新しく見る時には、以下の処理をします。
- スタックの先頭にあるビル が を満たす限り、 をスタックから取り除く。このときビル にとってビル が「ビル より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」に該当する。
- スタックの先頭にビル を追加する。
この処理の過程で、スタックの中にあるビルは常に高さでソートされ、底にあるものほど高いビルになっています。そのため優先度付きキューなどではなくスタックで処理することができます。
このように列挙したジャンプ可能なビルの組の個数は であることが分かります。よって を「ビル まで到達するためのジャンプ回数の最小値」とするDPを用いて計算量 で解くことができます。