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

Round #874 (Div. 3)

 

 

대회

https://codeforces.com/contest/1833

Dashboard - Codeforces Round 874 (Div. 3) - Codeforces

 

 

푼 문제

A. Musical Puzzle

입력받은 문자열에서 연속된 두 글자의 종류의 수를 출력하면 된다. 중복되는 부분 문자열 처리를 위해 map 자료구조를 사용했다.

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    int n;
    cin >> n >> s;
    map<string, int> M;
    for (int i = 0; i < n - 1; i++) {
      M[s.substr(i, 2)]++;
    }
    cout << M.size() << '\n';
  }
  return 0;
}

 

B. Restore the Weather

배열 a와 b를 정렬한 순서를 a의 원래 순서에 맞추어 b를 구성하면 된다. 따라서 a의 원소와 원래 index를 pair로 가지는 x라는 배열을 만들어준다. 배열 b와 x를 정렬하고 크기가 n인 ans 배열을 만들어준다. x의 앞에서부터(i = 0부터 n-1까지) 차례대로 저장되어 있는 원래 인덱스가 x[i].second 이므로 ans[x[i].second]에 b[i] 값을 넣어준다.

 

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n), ans(n);
    vector<pair<int, int>> x(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];
    for (int i = 0; i < n; i++)
      cin >> b[i];
    for (int i = 0; i < n; i++)
      x[i] = {a[i], i};
    sort(b.begin(), b.end());
    sort(x.begin(), x.end());
    for (int i = 0; i < n; i++)
      ans[x[i].second] = b[i];
    for (int i = 0; i < n; i++)
      cout << ans[i] << ' ';
    cout << '\n';
  }
  return 0;
}

 

 

C. Vlad Building Beautiful Array

b[i]에는 a[i] 또는 a[i]-a[j]가 들어갈 수 있다. 그리고 배열 b는 모든 원소가 짝수이거나 홀수여야 한다. 이 문제에서는 홀수-홀수=짝수임을 이용한다.

 

먼저 배열 a를 입력받을 때 홀수의 수를 센다. 홀수가 1개 이상인 경우에 가장 작은 원소를 m이라 하고 m이 홀수라면 b[i]에는 a[i]가 짝수라면 a[i]를, 홀수라면 a[i] - m은 짝수가 되므로 모든 원소가 짝수인 배열을 만들 수 있다. 가장 작은 원소를 선택하는 이유는 a[i] - a[j]가 음수가 되지 않도록 하기 위해서이다.

 

만약 홀수가 1개 이상인 경우에 m이 짝수라면 홀수 중 가장 작은 수는 홀수일 수 밖에 없으므로 불가능하다.

그리고 홀수가 0개인 경우는 모든 원소가 짝수이므로 이미 완성된 배열이다.

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, o = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] % 2)
        o++;
    }
    int m = *min_element(a.begin(), a.end());
    if (o >= 1) {
      if (m % 2) {
        cout << "YES\n";
      } else {
        cout << "NO\n";
      }
    } else {
      cout << "YES\n";
    }
  }
  return 0;
}

 

 

총평 및 여담

약 한달 반정도만에 참여한 대회였다. A, C는 꽤 빠르게 풀었다고 생각하는데 B를 첫 시도에 실패하고 D에 도전하다가 시간만 날렸다. 오랜만에 코드포스에 참여해 푼 사람 수를 확인하는 걸 까먹어서 푼 사람이 현저히 적은 D를 30분이나 붙잡고 있었다. D를 포기하고 B를 다시 금방 AC를 받아서 늦은 3솔로 퍼포먼스가 많이 내려간 것 같다. 아쉬움이 많이 남는 라운드였다.

 

!푼 사람 수 확인하면서 전략적으로 문제 풀기! + 업솔빙하기