コンテンツにスキップ

ABC481 B - Polyline

サイト
AtCoder
コンテスト
ABC481
問題
B - Polyline
難易度
78

xyxy 平面上の NN 個の点 (i,Ai)(i, A_i) を、点 1,2,…,N1, 2, \ldots, N の順に線分で結んで折れ線を作ります。この折れ線上(端点も含む)にある点のうち、yy 座標が KK であるものの個数を求める問題です(2≤N≤1002 \le N \le 100、Ai≠Ai+1A_i \ne A_{i+1})。

条件を満たす点は、次の 2 種類です。

  • Ai=KA_i = K である点 ii そのもの。
  • 点 ii と点 i+1i + 1 を結ぶ線分の内部の点で、AiA_i と Ai+1A_{i+1} の一方が KK より大きく、もう一方が KK より小さいとき。yy 座標が KK を横切るので、線分の内部にちょうど 1 個あります。

Ai≠Ai+1A_i \ne A_{i+1} なので、線分が y=Ky = K の上に重なることはありません。

ただし、隣り合う 2 本の線分が共有する端点を 2 回数えないように注意が必要です。そこで、点 11 は単独で数え、それ以降は線分ごとに「右端の点と線分の内部」だけを数えます。

点 i−1i - 1 と点 ii を結ぶ線分を見るとき、

  • Ai−1=KA_{i-1} = K なら、左端は前の線分(または点 11)ですでに数えています。Ai≠KA_i \ne K なので、この線分にはほかに条件を満たす点はありません。
  • そうでなければ、Ai=KA_i = K(右端)か、Ai−1A_{i-1} と AiA_i が KK をはさんでいる(内部)ときに、1 個数えます。

計算量は O(N)O(N) です。

Python
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
if A[0] == K:
ans += 1
for i in range(1, N):
if A[i - 1] == K:
continue
if A[i] == K or (A[i] > K) != (A[i - 1] > K):
ans += 1
print(ans)

A[i - 1] と A[i] がどちらも KK でないとき、(A[i] > K) != (A[i - 1] > K) は、2 点が y=Ky = K をはさんでいることを表します。