Kazun の競プロ記録

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

AtCoder Beginner Contest 297 A問題 Double Click

AtCoder ABC ABC297 A問題 100 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 回マウスをクリックし, 時刻 $i$ 回目のクリックは時刻 $T_i$ である.

時刻 $t_1, t_2$ に連続してクリックし, $t_2-t_1 \leq D$ のとき, 時刻 $t_2$ にダブルクリックが成立したという.

$N$ 回のクリックの間でダブルクリックは成立したクリックは存在するか? また, 成立するならば, 最初に性質したダブルクリックの時刻を求めよ.

制約

$1 \leq N \leq 100$
$1 \leq D \leq 10^9$
$1 \leq T_1 \lt T_2 \lt \dots \lt T_N \leq 10^9$

解法

$T$ が昇順に並べられているので, $i=2,3, \dots, N$ に対して, $i$ 回目のクリックでダブルクリックになるかどうかは $T_i-T_{i-1} \leq D$ かどうかで判定すれば良い.

よって, $i=2,3, \dots, N$ の順に $T_i-T_{i-1} \leq D$ かどうかを判定し, $T_i-T_{i-1} \leq D$ であった瞬間に $T_i$ を出力すれば良く, $i=N$ までみても解答が出なかった場合はダブルクリック不成立が答えになる.