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

Codeforces Educational Round #155 (Div. 2)

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

---

문제

A. Rigged! (AC+2 / 27 min)

힘은 들 수 있는 바벨 무게의 최대값, 지구력은 바벨을 들 수 있을 때 가능한 횟수다.

이 문제에선 첫 번째 선수가 우승하기 위한 바벨의 최소 무게를 구하는 문제다.

처음 입력되는 선수의 힘 s와 지구력 e를 기준으로 e가 더 높은 선수만 s, e를 pair로 벡터에 추가한 다음 힘을 기준으로 정렬한다.

만약 그런 선수가 없다면 첫 선수의 힘을 출력한다.

자신보다 힘이 강한 선수가 있다면 우승할 수 없으므로 -1을 출력한다.

자신보다 힘이 강한 선수는 없지만, 횟수를 같거나 많이 하는 선수가 있다면 그 선수가 들 수 있는 무게 + 1을 출력한다.

#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;
    vector<pair<int, int>> v;
    int x, y;
    cin >> x >> y;
    v.push_back({x, y});
    for (int i = 1; i < n; i++) {
      cin >> x >> y;
      if (y >= v[0].second)
        v.push_back({x, y});
    }
    sort(v.begin() + 1, v.end());
    if (v.size() == 1)
      cout << v[0].first << '\n';
    else if (v.back().first >= v[0].first)
      cout << -1 << '\n';
    else
      cout << v.back().first + 1 << '\n';
  }
  return 0;
}

 

B.Chips on the Board (AC / 51 min)

어떤 행 또는 열을 선택하더라도 반드시 한 칸 이상 색칠되어 있어야 한다. 배열 a와 b의 i번째 원소는 각각 i번째 행과 열을 선택했을 때 드는 비용이다. 이때 색칠되어 있는 칸의 비용은 a[i] + b[j]다. 위 조건을 만족하는데 필요한 최소 비용을 구하는 문제.

n × n 배열에서 최소 n개의 cell은 선택해야 위 조건을 만족할 수 있다. 즉, 계단 모양이 되던 직선이던간에 행 또는 열의 비용은 모두 들어간다.

그럼 두 가지 경우 밖에 남지 않는다.

1. 행의 모든 비용을 더한 값 + (열의 비용 중 최솟값 × n)
2. 열의 모든 비용을 더한 값 + (행의 비용 중 최솟값 × n)

최솟값 × n을 하는 이유는 어차피 n개의 셀을 골라야 하고 최소 비용을 구해야하니, 최소 비용인 행 또는 열을 애용하는 것이다.

실제로 저 둘 중 최솟값을 구해 출력하는 문제.

#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;
    cin >> n;
    vector<ll> a(n), b(n);
    ll sum_a = 0, sum_b = 0;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      sum_a += a[i];
    }
    for (int i = 0; i < n; i++) {
      cin >> b[i];
      sum_b += b[i];
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    ll ans = min(a[0] * n + sum_b, b[0] * n + sum_a);
    cout << ans << '\n';
  }
  return 0;
}

 

C. Make it Alternating (WA)

1과 0으로 이루어진 문자열에서 1과 0이 반복적으로 나타나도록 하기 위해서 문자를 지울 수 있다.

문자를 지우는 순서는 상관 없고(상관 있음 나중에 설명) 조건을 만족하도록 하는 최소 횟수를 구하는 문제다.

거기에 더해서, 이 최소 횟수를 만족하는 조합의 수를 구해야한다. <- 여기서 터짐. 딱봐도 dp 조합론이라 막막해져버렸다.

---

총평

첫 에듀 코포인데 웰논 위주로 나온다고 들었지만.. 나만 모르는 웰논이 너무 많은 듯 싶다. 공부를 더 열심히 해야할 것 같다.

dp dp dp dp dp 싫어 싫어 싫어 싫어 싫어