SCPC 2021 Round 1 후기 및 풀이

생각보다 잘봤다?

그동안 예선 기출 풀면서 2번까지만 스스로 풀 수 있었는데, 첫 실전에서 문제가 쉽게 나온 덕분인지 4번까지 만점을 받았다.

문제들이 거의 단순 구현으로 풀리는 경향이 있었던 것 같다...

2차에서도 좋은 결과를 얻고 싶다!

---

1번 친구들

 

풀이

• 친구 관계는 대칭적이므로 집합으로 표현할 수 있습니다
• 극대 그룹은 모든 사람이 각 집합에 포함되어 있는 상태입니다
  • 극대 그룹의 개수는 집합의 개수와 동일함을 알 수 있습니다
• Disjoint Set으로 문제를 해결할 수 있습니다
  • 친구 관계라면 union 연산으로 집합에 추가합니다
  • 전체 집합 개수를 count하여 극대 그룹을 찾습니다
• union 연산에 상수시간, $N$번 반복하므로 $O(N)$

소스코드

/*
    Prob
    2021 SCPC 1차 예선 1번 친구들
    Writer
    MyungSeung Kim(mskim9967@gmail.com)
*/

#include <bits/stdc++.h> 
#include <fstream>

using namespace std;

int tc, ans, n;
int a[100010], ds[100010];

int getSet(int a) {
    if(a == ds[a]) return a;
    return ds[a] = getSet(ds[a]);
}

void uni(int a, int b){
    if(a > b) swap(a, b);
    ds[getSet(b)] = a;
}

int main(void) {
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(0);

    cin >> tc;
    for(int tt = 1; tt <= tc; tt++) {
        ans = 0;
        for(int i = 1; i < 100010; i++) 
            ds[i] = i; // 집합 초기화

        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i];

        for(int i = 1; i <= n; i++)
            if(i + a[i] <= n) // 친구관계라면 집합에 추가
                uni(i, i + a[i]);

        for(int i = 1; i <= n; i++) // 집합의 개수=극대 그룹의 개수
            if(ds[i] == i) ans++;

        cout << "Case #" << tt << "\n";
        cout << ans << "\n";
    }
    return 0;
}

---

2번 이진수

/*
    Prob
    2021 SCPC 1차 예선 2번 이진수
    Writer
    MyungSeung Kim(mskim9967@gmail.com)
*/

#include <bits/stdc++.h> 
#include <fstream>

using namespace std;

int tc;
int n, t;
string b;
int a[50010];

int main(void) {
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(0); cout << fixed; cout.precision(7);

    cin >> tc;
    for(int tt = 1; tt <= tc; tt++) {
        memset(a, 0, sizeof(a));

        cin >> n >> t >> b;
        for(int i = 1; i <= n; i++) {
            if(b[i - 1] == '0') continue;

            if(i <= n - t && i > t) {
                if(a[i + t] == 0 && a[i - t] == 0) {
                    if(b[i - 1 + t + t] == '0') a[i - t] = 1;
                    else  a[i + t] = 1;
                }
            }
            else if(i <= n - t)
                a[i + t] = 1;
            else if(i > t)
                a[i - t] = 1;
        }

        cout << "Case #" << tt << "\n";
        for(int i = 1; i <= n; i++)
            cout << a[i];
        cout << "\n";
    }
    return 0;
}

---

3번 No Cycle

/*
    Prob
    2021 SCPC 1차 예선 3번 No Cycle
    Writer
    MyungSeung Kim(mskim9967@gmail.com)
*/

#include <bits/stdc++.h> 
#include <fstream>

using namespace std;

int tc;
int n, m, k;
int g[510][510];

void update(int a, int b) {
    if(g[a][b] == 1) return;
    g[a][b] = 1;
    for(int j = 1; j <= n; j++)
        if(g[j][a] == 1) update(j, b);
    for(int j = 1; j <= n; j++)
        if(g[b][j] == 1) update(a, j);
}

int main(void) {
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(0); cout << fixed; cout.precision(7);

    cin >> tc;
    for(int tt = 1; tt <= tc; tt++) {
        memset(g, 0, sizeof(g));

        cin >> n >> m >> k;
        for(int i = 0, a, b; i < m; i++) {
            cin >> a >> b;
            update(a, b);
        }

        cout << "Case #" << tt << "\n";
        for(int i = 0, a, b; i < k; i++) {
            cin >> a >> b;

            if(g[b][a] == 0) {
                cout << 0;
                update(a, b);
            } 
            else {
                cout << 1;
                update(b, a);
            }    
        }
        cout << "\n";
    }
    return 0;
}

4번 예약 시스템

• 살짝 노가다식

/*
    Prob
    2021 SCPC 1차 예선 4번 예약 시스템
    Writer
    MyungSeung Kim(mskim9967@gmail.com)
*/

#include <bits/stdc++.h> 
#include <fstream>

using namespace std;

int tc;
int n, m, oddCnt;
bool isOdd[20010];
int s[20010][4];
long long ans;

int main(void) {
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(0); cout << fixed; cout.precision(7);

    cin >> tc;
    for(int tt = 1; tt <= tc; tt++) {
        memset(s, 0, sizeof(s));
        memset(isOdd, 0, sizeof(isOdd));
        ans = 0;
        oddCnt = 0;
        int max1 = 0, max2 = 0, evenmax = 0;
        bool max1odd = false, max2odd = false;

        cin >> n >> m;
        for(int i = 0, l; i < n; i++) {
            cin >> l;
            if(l % 2 == 1) {
                isOdd[i] = true; 
                oddCnt++;
            }
            int a, b, c, d;
            a = b = c = d = 10000000;
            for(int j = 0, w; j < l; j++) {
                cin >> w;
                if(w < a) 
                    d = c, c = b, b = a, a = w;
                else if(w < b)
                    d = c, c = b, b = w;
                else if(w < c)
                    d = c, c = w;
                else if(w < d)
                    d = w;
            }
            s[i][0] = d, s[i][1] = c, s[i][2] = b, s[i][3] = a;
            if(c + d > max1) {
                max2 = max1, max1 = c + d;
                max2odd = max1odd, max1odd = l % 2;
            }
            else if(c + d > max2) {
                max2 = c + d;
                max2odd = l % 2;
            }

            if(isOdd[i]) {
                ans += d + c + b + a * 2;
            }
            else {
                ans += d + c + b + a;
                evenmax = max(evenmax, d + c);
            }
        }
        ans = ans - max1 - max2;

        if(oddCnt == 2 && max1odd && max2odd) {
            ans = ans + max2 - evenmax;
            long long newans = 0;
            for(int i = 0; i < n; i++) {
                if(isOdd[i]) newans += s[i][2] + s[i][3] * 2;
                else newans += s[i][3] * 2 + s[i][2] * 2 + s[i][1] + s[i][0];
            }
            ans = min(ans, newans);
        }


        cout << "Case #" << tt << "\n";

        cout << ans << "\n";
    }
    return 0;
}