ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps

Codeforces プログラミング競技プログラミング

お題箱より。

Problem - D - Codeforces

問題概要

$n$ 本のビルがあり、 $i$ 番目のビルの高さは $h_{i}$ である。

ビル $i$ からビル $j$ へは、 $i \lt j$ かつ以下の3条件のいずれか1つを満たす場合にジャンプして移動することができる。

$i+1 = j$ ：ビル $i, j$ は隣り合っている。
$\max(h_{i+1}, ..., h_{j-1}) \lt \min(h_{i}, h_{j})$ ：間にあるビルが全て、ビル $i, j$ の両方より低い。
$\min(h_{i+1}, ..., h_{j-1}) \gt \max(h_{i}, h_{j})$ ：間にあるビルが全て、ビル $i, j$ の両方より高い。

ビル $1$ からビル $n$ に到達するために必要なジャンプ回数の最小値を求めよ。

制約

$2 \le n \le 3\times 10^{5}$
$1 \le h_{i} \le 10^{9}$

解法

「間にあるビルが全て、ビル $i, j$ の両方より低い」という状況を図示します。

f:id:betrue12:20200911165521p:plain

ビルの組 $(i, j)$ が条件を満たしていて、図のように $i$ のほうが低い場合、もう一方のビル $j$ はビル $i$ から見て「自身より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」になっているという性質があります。そうでないもの、例えば $(i, x)$ や $(i, y)$ については条件を満たしません。

もしビル $j$ のほうが低ければ、逆にビル $i$ が「自身より左側にあり、自身以上の高さを持つビルのうち、最も近いもの」となります。ビル $i, j$ の高さが等しい場合は左右どちらから見た性質も成り立ちます。

そしてこの性質が成り立つことが、「間にあるビルが全て、ビル $i, j$ の両方より低い」という条件を満たすことの必要十分条件になっています。

よってこれらの性質を満たすビルの組 $(i, j)$ を探すことにします。逆パターンの「間にあるビルが全て、ビル $i, j$ の両方より高い」という条件も含めると、結局全てのビル $k$ について

ビル $k$ より右側にあり、自身以上の高さを持つビルのうち、最も近いもの
ビル $k$ より左側にあり、自身以上の高さを持つビルのうち、最も近いもの
ビル $k$ より右側にあり、自身以下の高さを持つビルのうち、最も近いもの
ビル $k$ より左側にあり、自身以下の高さを持つビルのうち、最も近いもの

を探せば良いことになります。これらを全て求めると「隣り合っているビルの組」も自動的に含まれるので、これでジャンプ可能なビルの組を網羅できます。

4パターン全てほぼ同様に解くことができるので、一例として「ビル $k$ より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」の求め方を考えます。これはスタックを使って解くと効率的です。

ビルを左から順番に見ていきます。ビル $j$ を新しく見る時には、以下の処理をします。

スタックの先頭にあるビル $k$ が $h_{k} \le h_{j}$ を満たす限り、 $k$ をスタックから取り除く。このときビル $k$ にとってビル $j$ が「ビル $k$ より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」に該当する。
スタックの先頭にビル $j$ を追加する。

この処理の過程で、スタックの中にあるビルは常に高さでソートされ、底にあるものほど高いビルになっています。そのため優先度付きキューなどではなくスタックで処理することができます。

このように列挙したジャンプ可能なビルの組の個数は $O(n)$ であることが分かります。よって $dp\lbrack i\rbrack$ を「ビル $i$ まで到達するためのジャンプ回数の最小値」とするDPを用いて計算量 $O(n)$ で解くことができます。

ACコード

Submission #92486700 - Codeforces