ABC481 B - Polyline
- サイト
- AtCoder
- コンテスト
- ABC481
- 問題
- B - Polyline
- 難易度
- 78
平面上の 個の点 を、点 の順に線分で結んで折れ線を作ります。この折れ線上(端点も含む)にある点のうち、 座標が であるものの個数を求める問題です(、)。
条件を満たす点は、次の 2 種類です。
- である点 そのもの。
- 点 と点 を結ぶ線分の内部の点で、 と の一方が より大きく、もう一方が より小さいとき。 座標が を横切るので、線分の内部にちょうど 1 個あります。
なので、線分が の上に重なることはありません。
ただし、隣り合う 2 本の線分が共有する端点を 2 回数えないように注意が必要です。そこで、点 は単独で数え、それ以降は線分ごとに「右端の点と線分の内部」だけを数えます。
点 と点 を結ぶ線分を見るとき、
- なら、左端は前の線分(または点 )ですでに数えています。 なので、この線分にはほかに条件を満たす点はありません。
- そうでなければ、(右端)か、 と が をはさんでいる(内部)ときに、1 個数えます。
計算量は です。
Python
N, K = map(int, input().split())A = list(map(int, input().split()))ans = 0if A[0] == K: ans += 1for i in range(1, N): if A[i - 1] == K: continue if A[i] == K or (A[i] > K) != (A[i - 1] > K): ans += 1print(ans)A[i - 1] と A[i] がどちらも でないとき、(A[i] > K) != (A[i - 1] > K) は、2 点が をはさんでいることを表します。