コンテンツにスキップ

DOJ Beginner Contest 6 C - Dadas Is Short

サイト
DOJ
コンテスト
DOJ Beginner Contest 6
問題
C - Dadas Is Short

NN 人が左から一列に並んでいて、ii 番目の人の身長は HiH_i です。ダダスは 11 番目の人です。

ダダスを含む連続した区間 [L,R][L, R] のうち、区間内でダダスの身長がほかの全員より真に高いものの個数を求める問題です。NN の総和は 3×1053 \times 10^5 以下です。

ダダスは 11 番目なので、区間は必ず L=1L = 1 です。数えるのは、H2,…,HRH_2, \dots, H_R がすべて H1H_1 より小さくなるような RR の個数です。

左から見ていき、Hi≥H1H_i \ge H_1 となる最初の ii を探します。条件を満たす RR は 1,2,…,i−11, 2, \dots, i - 1 の i−1i - 1 個です。そのような ii がなければ、R=1,…,NR = 1, \dots, N のすべてが条件を満たすので、答えは NN です。

Python
for _ in range(int(input())):
N = int(input())
H = list(map(int, input().split()))
for i in range(1, N):
if H[i] >= H[0]:
print(i)
break
else:
print(N)

コードは 0-indexed なので、H[i] >= H[0] となる最初の i がそのまま答えの i−1i - 1 にあたります。for 文の else は、break せずにループを終えたときに実行されます。