[코드포스 / Codeforces] Round #897 (Div. 2)

Round #897 (Div. 2)

 

 

대회

https://codeforces.com/contest/1867

Dashboard - Codeforces Round 897 (Div. 2) - Codeforces

 

 

푼 문제

A. green_gold_dog, array and permutation

입력받은 배열을 오름차순으로 정렬한 다음 원래 index의 위치에 1~N까지 위치하도록 한다. pair를 사용해 index를 함께 묶어서 정렬했다. 어렵지 않아서 코드만 봐도 이해가 될 듯.

#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;
    cin >> n;
    vector<pair<int, int>> a, b;
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      a.push_back({x, i});
    }
    sort(a.begin(), a.end(), greater<>());
    for (int i = 0; i < n; i++) {
      b.push_back({i + 1, a[i].second});
    }
    sort(b.begin(), b.end(), [](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });
    for (auto i : b)
      cout << i.first << ' ';
    cout << '\n';
  }
  return 0;
}

 

B. XOR Palindromes

지문 이해가 어려웠던 문제다. 한 시간이나 썼다..

팰린드롬이 아니도록 하는 쌍의 수를 파악하고, 1이 i(0~N)개일 때 에러 쌍을 해결하고 남은 1의 수로 case work.

0개면, 에러가 없으므로 가능

양수면, 에러가 남아있으므로 불가능

음수일 때가 조금 길다. 음수라는 것은 에러는 이미 해결했고 나머지를 적절히 배치해야 한다. 남은 것은 쓰기 편하게 -1을 곱해서 양수로 만들어준다. 먼저, 에러가 나지 않았던 쌍은 2개의 1을 사용해서 팰린드롬을 유지할 수 있다.

• 여기서 (남은 1의 수)가 에러가 나지 않았던 쌍을 다 뒤집을 만큼 남아있다면, 다 사용해 준다.
  • (남은 1의 수)가 0개면 모두 사용해서 팰린드롬을 유지했으니 가능
  • (남은 1의 수)가 1일 때, N이 홀수일 때(가운데 문자는 항상 팰린드롬을 만족할 때) 가운데에 배치해서 가능
  • 이외엔 모두 불가능
• 만약 쌍을 모두 뒤집을 만큼 충분하게 남지 않았다면
  • N과 (남은 1의 수)의 홀짝성이 같으면 가능
  • (남은 1의 수)가 짝수면 가능
  • 이외엔 모두 불가능

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

int cntErr(string s) {
  int cnt = 0;
  for (int i = 0; i < s.size() / 2; i++)
    if (s[i] != s[s.size() - 1 - i])
      cnt++;
  return cnt;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    string s, ans = "";
    cin >> n >> s;
    int err = cntErr(s);
    for (int i = 0; i <= n; i++) {
      int x = err - i;
      if (x == 0) {
        ans += '1';
      } else if (x > 0) {
        ans += '0';
      } else if (x < 0) {
        int left = -x;
        int half = n / 2;
        int available = half - err;
        if (left >= available * 2) {
          left -= 2 * available;
          if (left == 0)
            ans += '1';
          else if (n % 2 == 1 && left == 1) {
            ans += '1';
          } else {
            ans += '0';
          }
        } else {
          if (n % 2 == left % 2) {
            ans += '1';
          } else if (left % 2 == 0) {
            ans += '1';
          } else {
            ans += '0';
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

 

C. Salyg1n and the MEX Game

인터렉티브라서 TC가 맞는지 확인이 어려웠다.

입력받는 수는 반드시 직전에 출력한 수보다 작다는 조건을 잊어서 멀리 돌아갔다..또 2*n+1번 과정을 거치면 종료되는데, 이걸 직접 break를 걸었더니 틀린 것 같다. 이제야 보니 자동으로 멈출 때는 -1이 입력으로 들어오는 것 같다. 쓸데없는 WA만 두 번 받았다.

set으로 입력을 받아 정렬된 상태를 유지하고, x=0으로 두고 첫 원소부터 보면서 x와 원소가 같으면 x++ 한다. 그러면 MEX 값을 얻을 수 있고, 이를 출력하면 된다. 이후엔 상대가 입력하는 값을 그대로 따라 출력하면 된다.

#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;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      s.insert(a);
    }
    int x = 0, y;
    for (auto i : s)
      if (i == x)
        x++;
    while (1) {
      cout << x << endl;
      s.insert(x);
      cin >> x;
      if (x == -1)
        break;
      s.erase(x);
    }
  }
  return 0;
}

 

총평 및 여담

두 번째 참가하는 div2인데 3솔을 해서 기분은 좋으나, C에서 의미 없는 WA를 2번이나 받았고 AC를 받았더니 대회가 5분 남았어서 퍼포먼스가 낮다. 만년 뉴비인 주제에 그린 퍼포가 나왔으니 기뻐하는 게 맞지만.. 그래도 아쉬운 건 어쩔 수 없다.

코드포스는 참여해도 성적이 좋은 편이 아니고 많이 풀지도 못해서 게시물을 쓰는 게 의미가 있나 싶기도 하지만 그래도 기록용으로 간간히 써보려고 한다.