Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 235 B 問題

AtCoder ABC ABC235 B問題 200 pts

問題

提出解答

問題の概要

$N$ 個の台があり, $i$ 番目の台の高さは $H_i$ である.

最初, 一番左の台の上に立っている人は以下の規則に従ってできるだけ行動をする.

今立っている台が一番右の台でなく, 右隣の台の高さが今立っている台の高さよりも高いとき, 右隣の台に移動する.

最終的に立っている台の高さを求めよ.

制約

$2 \leq N \leq 10^5$
$1 \leq H_i \leq 10^9$

解法

実際にシミュレーションして答えを導くことができる. 実際には,

$i \gets 1$
$i \lt N$ かつ, $H_i \lt H_{i+1}$ である限り, $i \gets i+1$ とする.
$H_i$ を出力する.

という手順になる.