[코드포스 / Codeforces] Round #900 (Div. 3)

Codeforces Round #900 (Div. 3)

문제 세트는 여기서 확인할 수 있다.

---

문제

A. How Much Does Daytona Cost? (AC / 4 min)

n 크기의 배열의 서브세그먼트에서 k가 가장 빈도가 높은 수가 되도록 할 수 있는지 여부를 출력하는 문제.

서브세그먼트는 배열의 원소 하나도 가능하므로 배열에 k가 등장하면 YES 아니면 NO를 출력한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    int x;
    string ans = "NO";
    for (int i = 0; i < n; i++) {
      cin >> x;
      if (x == k)
        ans = "YES";
    }
    cout << ans << '\n';
  }
  return 0;
}

 

B.Aleksa and Stack (AC / 9 min)

3⋅𝑎[𝑖+2] is not divisible by 𝑎[i]+𝑎[𝑖+1] for each 𝑖 (1 ≤ 𝑖 ≤ 𝑛−2).

위 조건을 만족하는 배열을 만드는 문제. 홀수 두개의 합은 짝수고 3곱하기 홀수는 반드시 홀수이므로 모든 배열의 원소가 홀수이면 만족한다. 단, 배열은 반드시 오름차순이어야 하므로 1 3 5 7 ... 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
      cout << i * 2 + 1 << ' ';
    cout << '\n';
  }
  return 0;
}

 

C.Vasilije in Cacak (WA)

1~n까지 숫자 중 k개 숫자를 골라서 x를 만들 수 있는지 여부를 묻는 문제.

이런 저런 조건을 찾고 수를 마구마구 써보면서 시도했지만 WA를 받았다.

친구의 풀이에 납득은 했지만 이해는 안됐다.

앞에서부터 k개 고른게 x보다 크거나 뒤에서부터 k개 고른게 x보다 작으면 불가능하다는 점은 알겠다.

이외엔 모두 가능하다고 하는데 이 부분이 이해가 잘 되지 않는데.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t;
  cin >> t;
  while (t--) {
    ll n, k, x;
    cin >> n >> k >> x;
    if (k * (k + 1) / 2 > x || n * (n + 1) / 2 - (n - k) * (n - k + 1) / 2 < x)
      cout << "NO\n";
    else
      cout << "YES\n";
  }
  return 0;
}

 

E.Iva & Pav (WA)

n개의 수와 q개의 쿼리가 입력된다. 각 쿼리에선 l과 k가 입력된다. n개의 수에서 l번째 원소부터 적당한 r번째 원소까지의 모든 & 연산 결과가 k보다 크게 되는 가장 큰 r을 찾는 문제.

그냥 해봤다가 시간이 터짐과 동시에 내 머리도 터졌다.

---

총평

div 3에서 2솔. 이젠 좀 익숙하다. 해도 실력은 떨어지기만 하는 느낌이다. 그래도 해야지 뭐..