[Codeforces] Educational Codeforces Round 37 (Rated for Div. 2) 이야기

A. Water The Garden :: http://codeforces.com/contest/920/problem/A 

BFS로 문제를 해결하면 쉽게 풀 수 있다.

인풋의 값들이 BFS의 시작점이되는 값들이고 이 값들을 기점으로 퍼지도록 만들면 된다.

#include <iostream>
#include <cstdio>
#include <queue>
#include <memory.h>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int arr[1000];
bool visit[1000];
int main()
{
    int tc;
    cin >> tc;
 
    while (tc--)
    {
        memset(arr, -1, sizeof(arr));
        memset(visit, 0, sizeof(visit));
 
        int n, k;
        cin >> n >> k;
 
        queue<pii> q;
 
        for (int i = 1; i <= n; i++)
            arr[i] = 1;
 
        for (int i = 0; i < k; i++)
        {
            int val;
            cin >> val;
            q.push({ val, 1 });
        }
 
        int ans = 0;
        while (!q.empty())
        {
            int here = q.front().first;
            int cnt = q.front().second;
 
            q.pop();
 
            if (visit[here])
                continue;
 
            ans = max(cnt, ans);
            visit[here] = true;
 
            if (here - 1 >= 1 && arr[here - 1] && !visit[here - 1])
                q.push({ here - 1, cnt + 1 });
            if (here + 1 <= n && arr[here + 1] && !visit[here + 1])
                q.push({ here + 1, cnt + 1 });
        }
        cout << ans << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

B. Tea Queue :: http://codeforces.com/contest/920/problem/B

Naive하게 문제를 해결 할 수 있다.

3

1 5

1 1

2 3

테스트 케이스를 보면

1번애는 1~5초사이 teapot을 가질 수 있고

2번애는 1~1초사이 teapot을 가질 수 있고

3번애는 2~3초사이 teapot을 가질 수 있어서

1번과 2번이 같이 1초에 teapot을 가질 수 있을땐 번호가 빠른애가 그 시간에 가질 수 있게 된다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
 
using namespace std;
 
typedef pair<int, int> pii;
 
pii arr[1002];
bool visit[1002];
int ans[1002];
 
int main()
{
    int tc;
    cin >> tc;
    while (tc--)
    {
        memset(arr, 0, sizeof(arr));
        memset(visit, 0, sizeof(visit));
        memset(ans, 0, sizeof(ans));
        int n;
        cin >> n;
 
        int tmax = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i].first >> arr[i].second;
            tmax = max({ tmax, arr[i].first, arr[i].second });
        }
        int cnt = 0;
        for (int time = 1; cnt < n && time <= tmax; time++)
        {
            bool chk = false;
            for (int i = 0; i < n; i++)
            {
                if (!visit[i] && arr[i].first <= time && time <= arr[i].second)
                {
                    chk = true;
                    cnt++;
                    visit[i] = true;
                    ans[i] = time;
                    break;
                }
                else {
                    continue;
                }
            }
        }
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << endl;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

C. Swap Adjacent Elements :: http://codeforces.com/contest/920/problem/C 

연속된 1을 구성하는 각 구간에 대해 sort를 하여 원래대로 형성이 되는지 확인해주면 된다.

sort가 O(nlgn)이지만, 각 구간에 대해 O(n1lgn1) + O(n2lgn2) + ... + O(nklgnk) <= O(nlgn)이기에 시간복잡도에 구애받지 않는다.

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int arr[200002];
int tmp[200002];
int can[200002];
 
int main()
{
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        tmp[i] = arr[i];
    }
 
    sort(tmp, tmp + n);
 
    for (int i = 0; i < n - 1; i++)
        scanf("%1d", &can[i]);
 
    int start = 0, end = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (can[i] == 0)
        {
            sort(arr + start, arr + end + 1);
            start = i + 1, end = i + 1;
            continue;
        }
 
        else
        {
            end++;
        }
    }
    sort(arr + start, arr + end + 1);
    for (int i = 0; i < n; i++)
        if (arr[i] != tmp[i])
            return !printf("NO");
 
    return !printf("YES");
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

E. Connected Components? :: http://codeforces.com/contest/920/problem/E 

문제에서 주어지는 인풋을 제외한 모든 간선이 연결되어있을때 컴포넌트의 수와 각 컴포넌트의 크기를 구해야 한다.

여기서 조심해야 할 부분은 set으로 구성하지 않고 vector로 구성하면 TLE를 받게 되니 조심하자.

set으로 erase를 하면 O(lgn)이지만, 벡터는 O(n)이라 시간 복잡도에서 밀리게 된다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
using namespace std;
 
vector<int> vc[200002];
set<int> st;
bool visit[200002];
 
int main()
{
    int n, m;
    
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        vc[from].push_back(to);
        vc[to].push_back(from);
    }
 
    for (int i = 1; i <= n; i++)
    {
        st.insert(i);
        sort(vc[i].begin(), vc[i].end());
    }
 
    vector<int> ans;
    for (int i = 1; i <= n; i++)
    {
        if (visit[i])
            continue;
 
        int cnt = 1;
        queue<int> q;
        q.push(i);
        st.erase(i);
 
        while (!q.empty())
        {
            int here = q.front();
            q.pop();
 
            for (auto it = st.begin(); it != st.end(); )
            {
                // it는 내가 가고자 희망하는 정점을 이야기하고
                // tmp는 해당하는 정점으로 갈 수 없는곳이거나 end()이다.
                // 즉 *tmp != *it는 '내가 가고자 하는곳이 갈수 없는 정점이 아니라면'과 동치
                auto tmp = lower_bound(vc[here].begin(), vc[here].end(), *it);
 
                if (tmp == vc[here].end() || *tmp != *it)
                {
                    q.push(*it);
                    visit[*it] = true;
                    st.erase(it++);
                    cnt++;
                }
                else
                    it++;
            }
        }
 
        ans.push_back(cnt);
    }
 
    sort(ans.begin(), ans.end());
 
    cout << ans.size() << endl;
    for (auto i : ans)
        cout << i << " ";
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>