【AtCoder】ABC 481 B - Polyline

B - Polyline

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 78 / NoviSteps: 5Q / 配点: 200 点

問題概要

$xy$ 平面上に $N$ 個の点があり、点 $i$ の座標は $(i,A_i)$ である。

$i=1,2,\ldots,N-1$ について点 $i$ と点 $i+1$ を線分で結び、$1$ 本の折れ線を作る。

この折れ線上(端点も含む)にある点のうち、$y$ 座標が $K$ であるものの個数を求めよ。

ただし、制約より条件を満たす点の個数は有限であることが保証される。

制約

• $2 \le N \le 100$
• $1 \le A_i \le 100$ $(1 \le i \le N)$
• $A_i \ne A_{i+1}$ $(1 \le i < N)$
• $1 \le K \le 100$
• 入力される値はすべて整数

考察

頂点が $y = K$ に一致する場合と、線分の内部で $y = K$ を横切る場合を分けて数える。

前者は単純に $A_i = K$ となる $i$ の個数を数えればよい。

後者については、$A_i < K < A_{i+1}$ または $A_i > K > A_{i+1}$ となる $i$ の個数を数えればよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N, K;
11.    cin >> N >> K;
12.    vector<int> A(N);
13.    rep(i, 0, N) cin >> A[i];
14. 
15.    int ans = 0;
16.    rep(i, 0, N) {
17.        if (A[i] == K) ans++;
18.    }
19. 
20.    rep(i, 0, N - 1) {
21.        if ((A[i] < K && K < A[i + 1]) || (A[i] > K && K > A[i + 1])) {
22.            ans++;
23.        }
24.    }
25. 
26.    cout << ans << endl;
27. 
28.    return 0;
29.}

https://atcoder.jp/contests/abc481/submissions/80307302

atcoder.jp

実装時間: 5 分

コメント

綺麗に書こうとしたら逆に時間かかってしまった。