Codeforces Round #574 (Div.2) 후기/풀이

유럽여행 이후 첫번째 라운드

3주동안 코딩을 안한게 티가 난다...라기보다는, 그냥 B번 뇌절에서 끝났다. E번은 어차피 못푸는 문제였고.

 

Rating Change : -24 (1809 -> 1785)

Performance : 1705

---

문제 풀이

A. Drinks Choosing

각 학생이 선호하는 음료를 최대한 주고 싶은데, 2개짜리 페어만 살 수 있다. 그리고 음료가 1캔 이상 남을 수 없다.

짝수명이 선호하는 음료는 그대로 사다 주면 되고, 홀수명이 선호하는 음료는 1명씩 남긴다음 그중에 임의로 반을 골라서 그사람들에게 원하는걸 준다음 나머지는 그냥 막 주는 것이 최선임을 알 수 있다. 

#include <bits/stdc++.h>
int arr[1010];
int main()
{
    int odd = 0;
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        arr[x]++;
    }
    for (int i = 0; i< 1010; i++)
        if (arr[i]%2)
            odd++;
    cout << n-odd/2;
}

---

B. Sport Mafia

연산 두 가지가 주어진다.

1번 : 사탕의 개수를 (지금까지 1번 연산이 수행된 횟수 + 1) 만큼 늘린다.

2번 : 사탕의 개수를 1개 줄인다.

총 연산 횟수 $n$ 번과 최종 남은 사탕 수 $k$개가 주어질 때, 2번 연산이 수행된 횟수를 찾는다.

 

$k$ 가 10억 이하이고, $n$도 10억 이하이므로 일단 몇십억개의 사탕이 있었다면 절대 답이 될 수 없다. 많아야 20억개 이하의 사탕에서 출발해야 하므로, 1번 연산은 많아야 수만 번.

 

따라서, 1번 연산의 수 $i$를 올려가면서 테스트하면 된다. 일단 $i$번 1번연산이 들어갔다면, 사탕 $\frac{i(i+1)}{2}$ 개에서 시작해서 2번연산을 $n-i$번 해서 줄인 값이 $k$개가 맞는지 보면 되니까.

 

그런데 TLE를 계속 받았다. 도대체 왜 TLE가 나는지 전혀 이해를 못한채로 3번을 내본 후, 포기하고 C번을 풀러 갔다가 C, D1을 풀고 한참 뒤에 돌아와서 찾았는데, 

for (int i = 0; i<= 1010100; i++)
	ll p = i*(i+1)/2;

여기에서, $i$가 몇만 이상 갈 때, $p$에 값을 집어넣기 전에 계산을 먼저 하므로 오버플로우가 난다..

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int main()
{
    ll n, k;
    cin >> n >> k;
    for (ll i = 0; i<=1010100; i++)
    {
        ll p = (i*(i+1))/2;
        if (p<k)
            continue;
        if (p-(n-i)==k)
        {
            cout << n-i;
            return 0;
        }
    }
    return 0;
}

사실 의미없는 continue같은건 왜 TLE나는지 이해를 못해서 넣어 본건데, 당연히 의미가 없다. 끝에 return 0; 도 필요 없고.

---

C. Basketball Exercise

1행과 2행의 학생 중, 어떤 줄에서도 연속한 2명을 뽑을 수 없고, 바로 전에 뽑은 학생보다 큰 번호의 학생만 뽑을 수 있을 때, 키의 총합을 최대화하는 문제.

단순한 dp문제이므로 그냥 코딩하면 된다. 

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define usecppio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
 
int dp[101010][2];
int arr[101010][2];
int32_t main()
{
    usecppio
    int n;
    cin >> n;
    for (int i = 1; i<=n; i++)
        cin >> arr[i][0];
    for (int i = 1; i<=n; i++)
        cin >> arr[i][1];
    for (int i = 1; i<=n; i++)
    {
        dp[i][0] = max(dp[i-1][1]+arr[i][0], dp[i-1][0]);
        dp[i][1] = max(dp[i-1][0]+arr[i][1], dp[i-1][1]);
    }
    cout << max(dp[n][0],dp[n][1]);
}

---

D. Submarine in the Rybinsk Sea

구현하기 진짜 심하게 귀찮은 문제인데, 간단히 요지는 이렇다.

$f(a, b)$ 는 정수 두 개를 받아서 정수를 뱉는 함수인데, 이런 식으로 구성한다.

$$f(123, 456) = 142536$$

$$f(456, 123) = 415263$$

그리고 두 숫자의 길이가 다르면, 이런 식으로 남은 것들을 앞에 붙인다.

$$f(7777, 888) = 7787878$$ 

배열 A가 주어졌을 때, 

$$\sum_{i, j \in A} f(i, j)$$ 의 값을 구하는 문제.

 

잘 생각해 보면, $f(a, b)$의 값에서, '$a$의 기여분' 은 $b$가 몇인지는 관계가 없다. $b$가 몇 자리 숫자인지가 관련이 있을 뿐.

따라서, 배열에서 미리 한자리 수가 몇개인지, 두자리 수가 몇개인지.... 를 세고,

한자리 수가 뒤에 올 때 $a$의 기여도, 두자리 수자 뒤에 올 때 ... 를 각각 해주면 된다. 숫자가 최대 9자리이므로 9번을 하면 되고, 숫자는 최대 10만 개이므로 최대 10만 * 9 * 9 해서 대략 천만 번 정도의 연산을 필요로 하는데, 실제로는 한 번 과정에서 모듈러 등등을 꽤 많이 써야 하므로 몇천만 정도의 연산이 필요하지만 아무튼 시간 안에는 잘 돌아 간다. 

 

코드가 상당히 더럽고 길기 때문에, 링크로 대체

 

(코드 링크)

 

---

후기

B번 오버플로우로 5틀한거 외에는 딱히 특별한 부분은 없다. E번은 2D세그? PST? 2D Sparse Table? 아무튼 내가 모르고 못 짜는 자료구조를 요구하게 생긴 문제인 것으로 보인다. 시간복잡도도 $\mathcal{O((n+m)\log(n+m)}$ 같은 얘기들을 하는 걸 보니 아무튼 내가 2시간 잡았어도 못 풀었을 문제니까. 

풀 수 있는 문제를 다 풀었다는 점은 좋지만, B번같은 실수만 안했으면 좋겠다. 그럴 수 있었으면 진즉에 퍼플 갔었겠지만.