코드포스 - Codeforces Round #544 (Div. 3)

개강하고 첫 코포 한 날이였다. 

A. Middle of the Contest

예제를 읽고 문제를 대충 보니 두 시각이 주어지고 그 시각의 중간을 출력하면 되는 간단한 문제이다.

ex) 10시하고 11시의 중간은 10시 30분

여기서 조심해야할 부분은 예제 3번처럼 2분이면 02분으로 출력해야한다. 하지만 이 처리는 매우 쉬운것으로 빠르게 처리하고 AC를 받았다.

#include<stdio.h>
 
int main()
{
    int a,b,c,d;
    scanf("%d:%d",&a,&b);
    scanf("%d:%d",&c,&d);
    b+=a*60;
    d+=c*60;
    a=(b+d)/2/60;
    b=(b+d)/2%60;
    printf("%02d:%02d",a,b);
    return 0;
}

B. Preparation for International Women's Day

두 번의 TLE을 가지면서 멍때리고 있었다. 집에 도착하자마자 바로 컴퓨터를 키고 시작한거여서 그런지 집중이 안됬었다. 다시 차근차근 보는데 미리 k로 나눈 나머지를 이용해서 쓱싹하면 된다는것을 늦게 보였다..

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
 
using namespace std;
typedef long long ll;
ll vc[1000];
 
ll ans;
int main()
{
    ll n, k, maxi=0;
    cin >> n >> k;
    for (ll i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        vc[t%k]++;
    }
 
    for (ll i = 0; i <= k / 2; i++)
    {
        if (i == 0 || i == k - i)
        {
            ans = ans + (vc[i] - (vc[i] % 2));
        }
        else 
        {
            int t = min(vc[i], vc[k - i]);
            ans = ans + t+t;
        }
    }
    cout << ans;
    return 0;
}

C. Balanced Team

이 문제를 보자마자 바로 각이 보여 코딩을 해 AC를 받았던 문제이다. 

그냥 정렬하고 upper_bound 쓰면 되는 각이다 하고 간단히 풀었다. 만약 n의 크기가 더 컸더라면 upper_bound말고 투 포인터로 코딩 하면 된다.

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
 
using namespace std;
typedef long long ll;
vector<int> vc;
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        vc.push_back(t);
    }
    sort(vc.begin(), vc.end());
    ll ans = 0;
    for (int i = 0; i < vc.size(); i++)
    {
        ll t = upper_bound(vc.begin(), vc.end(), vc[i] + 5) - vc.begin() - i;
        ans = max(ans,t);
    }
    cout << ans;
    return 0;
}

F1. Spanning Tree with Maximum Degree

div 3에서 자주 보였던 MST가 또 나왔다. 정렬을 Degree가 큰 거부터 정렬하고 MST를 만들면 되는 간단한 문제였다.

#include<iostream>
#include<vector>
#include<cstring>
#include<tuple>
#include<queue>
#include<algorithm>
 
using namespace std;
 
#define tp tuple<int, int, int>
#define GET(x,a) get<a>(x)
vector<vector<int>> vc;
vector<tp> c;
int cost[200005];
int uf[200005];
 
int find(int x)
{
    if (uf[x] == -1)return x;
    else return uf[x] = find(uf[x]);
}
 
bool merge(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b)return false;
    uf[b] = a;
    return true;
}
 
int main()
{
    int n, k;
    cin >> n >> k;
    memset(uf, -1, sizeof(uf));
    vc.resize(n + 1);
    for(int i=0;i<k;i++)
    { 
        int a, b;
        cin >> a >> b;
        vc[a].push_back(b);
        vc[b].push_back(a);
        cost[a]++;
        cost[b]++;
    }
    for (int i = 1; i <= n; i++)
        for (auto j : vc[i])
            c.push_back(make_tuple(cost[i],i,j));
 
    sort(c.begin(), c.end(),greater<tp>());
 
    int cnt = 0;
    for (int i = 0; i < c.size(); i++)
    {
        int a = GET(c[i],1);
        int b = GET(c[i],2);
        if (merge(a, b))
        {
            cout << a << ' ' << b << '\n';
            if (++cnt == n - 1)break;
        }
    }
    return 0;
}