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

끝없이 고통받은 라운드. 시험때문에 PS를 못했더니 바로 실력 떡락한게 티가 나는 것 같다.

 

Rating Change : -39 (1858 -> 1819) 

Performance : 1710

 

---

문제 풀이

 

A. Ropewalkers 

생각보다 A번치고는 귀찮은 구현이었다고 생각했는데, 몇줄에 끝낸 사람이 꽤 있는 것 같았다.

$a$, $b$, $c$ 가 주어졌을 때, 1초에 1씩 움직이면서 (한번에 하나만 움직일 수 있다)

임의의 두 개 사이의 거리가 $d$ 보다 크게 하는 최소 시간을 찾는 문제.

 

세 숫자를 정렬한 다음, 가운데 것을 움직이는 것과 양쪽 끝을 움직이는 것 중 무엇이 더 나은 해인지 확인하면 된다.

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

int arr[3];
int main()
{
    int d;
    cin >> arr[0] >> arr[1] >> arr[2] >> d;
    sort(arr,arr+3);
    int d1 = arr[1]-arr[0];
    int d2 = arr[2]-arr[1];
    int a1 = (d-min(d,d1))+(d-min(d,d2));
    int a2 = INT_MAX;
    if (d1+d2>=2*d)
        a2 = min((abs(arr[1]-arr[0]-d)),(abs(arr[1]-arr[2]+d)));
    cout << min(a1,a2);
}

---

B. Email from Polycarp

이번 라운드가 뭔가 잘못 돌아가고 있다는 생각이 들기 시작한 문제. 

문자열 S와 T가 주어졌을 때, "고장난 키보드로 S를 타이핑해서 T를 만들 수 있는지" 판정하는 문제이다.

고장난 키보드는 키 c가 입력되었을 때 c를 입력하고 싶은 횟수보다 많거나 같은 수만큼 입력해 준다.

즉, 2번을 입력하려고 하면 2번이 입력될 수도 있고, 4번이 입력될 수도 있고...

이게 무슨 소리인가 싶을 수도 있지만, 눌려서 안돌아오는 키보드로 hello를 입력하려다 보면 hhellllooo 같은게 입력될 수 있다 라는 정도로 보면 된다.

같은 문자들을 그룹으로 묶어놓고, S랑 T를 쭉 돌면서 '같은 문자가 나오는지', 'T에서 많거나 같은 횟수 나오는지' 

돌면 끝인데, 이걸 짜려고 무슨 $\texttt{vector <pair<char, int>>}$ 같은걸 만들어서 난리를 치느라 늦어졌다.

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

typedef pair<char,int> pci;
string str1;
string str2;
string tmp;
vector <pci> v;
vector <pci> v2;
int main()
{
    usecppio
    int n;
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        v.clear();
        v2.clear();
        str1.clear();
        tmp.clear();
        cin >> str1 >>tmp;
        int s1 = str1.size();
        int s2 = tmp.size();
        v.push_back({str1[0],1});
        for (int j = 1; j<s1; j++)
        {
            if (v.back().first==str1[j])
                v.back().second++;
            else
                v.push_back({str1[j],1});
        }

        v2.push_back({tmp[0],1});
        for (int j = 1; j<s2; j++)
        {
            if (v2.back().first==tmp[j])
                v2.back().second++;
            else
                v2.push_back({tmp[j],1});
        }

        int vs1 = v.size();
        int vs2 = v2.size();
        if (vs1!=vs2)
        {
            cout << "NO\n";
            continue;
        }
        bool flag = true;
        for (int k = 0; k<vs1; k++)
        {
            if (v[k].first==v2[k].first)
            {
                if (v[k].second<=v2[k].second)
                    continue;
                else
                {
                    flag = 0;
                    break;
                }
            }
            else
            {
                flag = 0;
                break;
            }
        }
        if (!flag)
        {
            cout << "NO\n";
            continue;
        }
        cout <<"YES\n";
    }
}

이걸 왜 이렇게 길게 짜야 하지..? ㅠㅠ

---

C1. Exam in BerSU (easy)

각각의 a[i] 에 대해, 1~(i-1) 번 까지의 원소들 중 최소한 $k$개를 빼야 1~i번까지의 남은 원소들의 합이 $M$ 보다 작아진다고 할 때, $k$를 찾는 문제이다. 

세그먼트 트리 같은걸 써서 어떻게 잘 해볼 수도 있었을 것 같지만, Div2 C에 그런걸 내진 않았을 거 같고....

C1은 배열의 원소가 100개, C2는 10만 개다. 즉, C2는 적어도 $\mathcal{O}(n \log n)$ 시간 정도에 결과를 내야 한다는 얘기인데, 처음에 꽤 오랜 시간 생각을 하다가 priority queue 를 잘 이용하면 될 것 같다는 생각이 들었다.

 

우선은 C1을 $\mathcal{O}(n^2 \log n)$ 의 Naive 구현으로 대충 뚫어놓고, C2를 구현하다가 시간이 40분 정도 지났다. (그리고 결국 못 풀었다)

 

C1 Naive 구현

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


int n, m;
int arr[202020];
ll prefsum[202020];
ll solve(int p)
{
    ll time = prefsum[p];
    priority_queue<int> pq;
    for (int i = 1; i<p; i++)
        pq.push(arr[i]);
    ll ans = 0;
    while(time>m)
    {
        ll x = pq.top();
        time -= x;
        ans++;
        pq.pop();
    }
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    for (int i = 1; i<=n; i++)
    {
        scanf("%d",arr+i);
        prefsum[i] = prefsum[i-1]+arr[i];
    }
    for (int i = 1; i<=n; i++)
        printf("%lld ",solve(i));
}

C2는, 두 priority queue가 원소를 막 주고받는 이상한 코드를 작성하고 틀렸다. 대충 알고리즘은 맞은 것 같은데, 뭔가 구현상에 많은 문제가 있는 것 같다. 

---

D. Extra Element

$n$개짜리 배열에, 1개를 뺀 다음 남은 $n-1$개를 어떻게 잘 배열해서 등차수열을 만들 수 있는지 판정하고, 된다면 뭘 빼야 할지 고르면 된다.

 

약간의 관찰로 다음 네 가지 경우 중 하나임을 알 수 있다. 먼저 주어진 배열을 정렬한 다음,

- 첫 번째 (가장 작은 원소) 를 빼서 등차수열을 만들 수 있거나

- 마지막 (가장 큰 원소) 를 빼서 등차수열을 만들 수 있거나

- 중간에 있는 것중 하나를 빼서 등차수열을 만들 수 있거나

- 등차수열을 만들 수 없다.

 

굉장히 당연한 얘기인데, 이렇게 쓰는 이유는

1, 2, 3 번 경우에 대해 우리는 초항과 마지막 항, 그리고 항의 개수 ($n-2$개) 를 알고 있으므로, 공차 $d$가 결정되어 버린다 ($d = \frac{a_{n-1} - a_1}{n-2}$) 

따라서, 공차를 알고 있으므로 각 항들이 이 경우에 맞는지 아닌지를 쉽게 판정할 수 있고, 3번 케이스의 경우 한 개가 맞지 않는 것을 허용해 주면 파악하기 어렵지 않다.

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;

typedef pair<int,int> pii;

int n;
vector <pii> v;
int pos;
bool check_1()
{
    int first = v[0].first;
    int last = v[n-1].first;
    if ((last-first)%(n-2))
        return 0;
    int d = (last-first)/(n-2);
    int tol = 0;
    int tmp = 0;
    for (int i = 0; i<n; i++)
    {
        if (v[i].first == first+(i-tol)*d)
            continue;
        else
        {
            tol++;
            tmp=v[i].second;
        }
        if (tol>1)
            return false;
    }
    if (tol==0)
        return 0;
    pos = tmp;
    return true;
}

bool check_2()
{
    int first = v[0].first;
    int last = v[n-2].first;
    if ((last-first)%(n-2))
        return 0;
    int d = (last-first)/(n-2);
    for (int i = 0; i<n-1; i++)
    {
        if (v[i].first == first+(i)*d)
            continue;
        else
            return false;
    }
    pos = v[n-1].second;
    return true;
}

bool check_3()
{
    int first = v[1].first;
    int last = v[n-1].first;
    if ((last-first)%(n-2))
        return 0;
    int d = (last-first)/(n-2);
    for (int i = 1; i<n; i++)
    {
        if (v[i].first == first+(i-1)*d)
            continue;
        else
            return false;
    }
    pos = v[0].second;
    return true;
}

int main()
{
    scanf("%d",&n);
    for (int i = 1; i<=n; i++)
    {
        int x;
        scanf("%d",&x);
        v.push_back({x,i});
    }
    sort(all(v));
    if (n<=3)
    {
        printf("1");
        return 0;
    }
    if (check_1()||check_2()||check_3())
    {
        if (pos == 0)
            return -1;
        printf("%d",pos);
        return 0;
    }
    else
    {
        printf("-1");
        return 0;
    }
}

---

후기 (Whining) 

라운드가 끝나고 댓글에서도 제기되었던 이야기인데, Codeforces의 서브태스크 문제가 약간 배점이 이상하게 잡혀 있다. 그래서, C2번을 한번에 푸는것보다 일단 빠르게 C1을 긁고 C2를 푸는게 (심지어 C1을 긁고 G1을 긁는 게) 이득을 보는, 뭔가 직관적이지 못한 구조를 가지고 있다. Mike Mirzayanov(CF 관리자) 도 이 문제를 인지하고 있는 것 같으니 어떤 식으로든 고쳐지긴 할 것 같다.

 

그걸 떠나서, 이번 라운드에서 구현을 너무 못했다. 간단한 것도 계속 뇌절하고...

구현 연습을 조금 더 빡세게 돌아야 할 것 같다.