[코드포스 / Codeforces] Round #859 (Div. 4)

Round #859 (Div. 4)

 

 

대회

https://codeforces.com/contest/1807

Dashboard - Codeforces Round 859 (Div. 4) - Codeforces

 

 

푼 문제

A. Plus or Minus

a, b, c를 입력받아 a+b=c가 성립하는지 여부를 출력하는 간단한 문제다.

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b == c)
      cout << "+\n";
    else
      cout << "-\n";
  }
  return 0;
}

 

 

B. Grab the Candies

Mihai가 Bianca보다 사탕을 많이 가지고 있는지 판단하는 문제다. Mihai가 가진 사탕의 수는 짝수의 합이고 Bianca가 가진 사탕의 수는 홀수의 합이다. 따라서 각 합을 구하고 비교하는 문제다.

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n, a = 0, b = 0;
    cin >> n;
    while (n--) {
      int x;
      cin >> x;
      if (x % 2 == 0)
        a += x;
      else
        b += x;
    }
    if (a > b)
      cout << "YES\n";
    else
      cout << "NO\n";
  }
  return 0;
}

 

 

C. Find and Replace

같은 문자를 모두 1 또는 0으로 바꾸어 1010101...처럼 교차되도록 만들 수 있는지 여부를 출력하는 문제다. 문자열에서 어떤 문자가 짝수 번째에 나왔다면 같은 문자는 반드시 짝수 번째에 나와야 하고 홀수일 때도 마찬가지다. 그렇지 않으면 1 또는 0이 연속되는 구간이 발생하기 때문이다. 따라서 같은 문자의 인덱스가 다른 경우가 있다면 NO를 출력한다.

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n, flag = 0;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
      int index = 0, tmp = (i + 1) % 2;
      while (s.find(s[i], index) != string::npos) {
        int idx = s.find(s[i], index) + 1;
        if (idx % 2 != tmp) {
          flag = 1;
          break;
        }
        index = idx;
      }
    }
    if (flag)
      cout << "NO\n";
    else
      cout << "YES\n";
  }
  return 0;
}

 

 

D. Odd Queries

배열의 l부터 r까지 원소를 k라고 가정했을 때 배열의 모든 원소의 합이 홀수인지 짝수인지 판단하는 문제다.

처음엔 (0번 ~ l-1번까지의 합) + k * (r - l + 1) + (r+1번부터 마지막까지의 합)을 일일이 구했으나 TLE를 받고 누적 합 배열을 구현해서 AC를 받았다.

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n, q;
    cin >> n >> q;
    vector<int> v(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      int x;
      cin >> x;
      v[i] = v[i - 1] + x;
    }
    while (q--) {
      int l, r, k;
      cin >> l >> r >> k;
      int sum = v[l - 1];
      sum += k * (r - l + 1);
      sum += v[n] - v[r];
      if (sum % 2)
        cout << "YES\n";
      else
        cout << "NO\n";
    }
  }
  return 0;
}

 

 

업솔빙

G1. Subsequence Addition (Easy Version)

대회 시간에는 풀지 못했지만 업솔빙해서 해결했다. 연산을 거쳐 입력받은 배열을 만들 수 있는지 여부를 확인하는 문제다. 각 원소를 오름차순으로 정렬했을 때 i번째 원소의 값은 0번째 원소부터 i-1번째 원소까지의 합보다 클 수 없다. 따라서 조건을 만족하지 않는 경우 NO를 출력하고 조건을 만족하지 않는 경우가 없을 경우 마지막에 YES를 출력한다. 추가로 원소가 1개일 때는 원소는 반드시 1이어야 한다.

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n, flag = 0;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
      cin >> v[i];
    sort(v.begin(), v.end());
    if (v[0] != 1) {
      cout << "NO\n";
      continue;
    }
    string ans = "YES\n";
    int s = 1;
    for (int i = 1; i < n; i++) {
      if (v[i] > s) {
        ans = "NO\n";
        break;
      }
      s += v[i];
    }
    cout << ans;
  }
  return 0;
}

 

 

G2. Subsequence Addition (Hard Version)

G1 문제와 같은 문제이고 차이점은 수의 범위가 int 범위를 초과하기 때문에 long long으로 바꿔주면 된다.

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n, flag = 0;
    cin >> n;
    vector<long long> v(n);
    for (int i = 0; i < n; i++)
      cin >> v[i];
    sort(v.begin(), v.end());
    if (v[0] != 1) {
      cout << "NO\n";
      continue;
    }
    string ans = "YES\n";
    long long s = 1;
    for (int i = 1; i < n; i++) {
      if (v[i] > s) {
        ans = "NO\n";
        break;
      }
      s += v[i];
    }
    cout << ans;
  }
  return 0;
}

 

 

총평 및 여담

첫 코드포스 참여였다. 참가하기 위해 당일 바로 아이디도 만들었다. 겁먹고 있었는데 Div.4라 그런지 생각했던 것보단 쉬웠다. 영어 지문 읽느라 집중력 소모가 심하고 제대로 이해한 게 맞는지 확신이 없어서 테스트 케이스를 죄다 해보느라 제출 시간이 늦어졌다.

E는 인터렉티브 문제라 바로 넘겼고 F도 구현이 너무 힘들어서 포기했다. G1과 G2는 대회 끝나고 업솔빙해서 풀긴 했는데 이렇게 간단한 거였다니.. 풀이를 구해내는 법도 연습이 필요할 것 같다.