Road to Expert Round 4

Road to Expert 라는, 그린~민트 -> 블루를 위한 한국인 Codeforce Group이 생겼다는 얘기를 듣고

블루에서 끝없이 뇌절로 떡락해서 온 민트지만 아무튼 민트니까 참여해 보기로 했다.

그룹장님이 3문제 단축셋을 준비해 주시는데,

월요일은 800-900-1000, 수요일은 900-1100-1300, 금요일은 1100-1300-1500 정도라고 한다.

 

사실 지금 현재 내 레이팅을 생각해보면 금요일 1500 외에는 바로바로 풀어내야 맞긴한데,

세세한 구현실력도 연습할겸 해서 그냥 앞으로 시간되는만큼은 돌아보려고 한다.

 

A. Right-Left Cipher

원본 문제 : Technocup 2019 - Elimination Round 4 A번

어떤 String S에 대해서, T가 다음과 같이 구성된다.

...S[7] S[5] S[3] S[1] S[2] S[4] S[6]...

이때 T로부터 다시 S를 복원하는 문제.

길이의 홀짝성에 맞춰서 적당히 짜주면 된다.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    char str[100];
    scanf("%s",str);
    int s = strlen(str);
    vector <char> v1;
    vector <char> v2;
    for (int i = 0; i<(strlen(str)+1)/2; i++)
        v1.push_back(str[i]);
    reverse(v1.begin(),v1.end());
    for (int i=(strlen(str)+1)/2; i<strlen(str); i++)
        v2.push_back(str[i]);
    for (int i = 0; i<(s/2); i++)
    {
        printf("%c",v1[i]);
        printf("%c",v2[i]);
    }
    s%2? printf("%c",v1[s/2]):1;
}

B. Getting an A

원본 문제 : Codeforces Round 491 Div.2 Problem B번

배열에서 몇개를 적당히 5로 바꿔서 평균을 4.5보다 높게 하려고 하는데, 최소 몇개를 바꿔야 할지 찾는 문제.

그리디하게 정답을 찾을 수 있다. 예를 들어, 4를 5로 바꿔서 정답이 나온다면, 3을 5로 바꿔도 항상 정답이 나올 것이기 때문.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    double total = 0;
    double arr[120];
    scanf("%d",&n);
    for (int i = 0; i<n; i++)
    {
        scanf("%lf",arr+i);
        total += arr[i];
    }
    sort(arr,arr+n);
    int c = 0;
    while((total/n)<4.5)
    {
        total += (5-arr[c]);
        arr[c] = 5;
        c++;
    }
    printf("%d",c);
}

C. Spyke Chatting

원본 문제 : Coder Strike 2014 Round 2 B번

$n$ 명의 직원이 $m$개의 채팅방에 메시지를 보내고, 각 직원이 들어가 있는 채팅방의 정보가 전부 주어져 있을 때, 

각 직원이 받은 문자의 개수를 구하는 문제.

 

직원은 많은 데 비해 (20만 명) 채팅방의 수는 작으므로 (10개), 각 채팅방에 몇개의 메시지가 올라가 있는지를 계속 추적하고, 각 직원들이 모든 채팅방에 보낸 메시지의 합을 각각 저장하면

 

"$k$번 직원이 들어가 있는 채팅방에 올라온 문자의 개수의 합 - $k$번 직원이 자기가 들어간 모든 채팅방에 보낸 문자의 개수의 합"

이렇게 $k$번 직원이 받은 문자 개수를 $\mathcal{O}(m)$ 시간에 구할 수 있다. 입력을 받으면서 모든 필요한 정보를 미리 처리해 둘 수 있기 때문.

 

#include <bits/stdc++.h>
#define PB push_back
using namespace std;
 
int emp[20200];
int chat[13];
vector <int> rec[20200];
int main()
{
    int n, m, k;
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 1; i<=n; i++)
    {
        for (int j = 1; j<=m; j++)
        {
            int tp;
            scanf("%d",&tp);
            if(tp)
                rec[i].PB(j);
        }
    }
    for (int i = 0; i<k; i++)
    {
        int a, b;
        scanf("%d%d",&a,&b);
        emp[a]++;
        chat[b]++;
    }
    for (int i = 1; i<=n; i++)
    {
        int tt = 0;
        for (auto it:rec[i])
            tt+=chat[it];
        tt-=emp[i];
        printf("%d ",tt);
    }
}