2021 SCPC Round 1 후기

결과

제주도 스쿠버 일정과 scpc일정과 겹쳐서 4시간 정도밖에 풀지 못했다. 2번까지 풀고 뒷 문제들이 크게 어려워 보이지 않았는데 다음 일정 때문에 못 풀어서 너무 아쉬웠다.

1. 친구들

N명의 사람이 있고, 각 사람은 d를 가지고 있는데 i번째 사람은 i + Di와 친구이다. i + Di > N이면 무시한다.

A와 B가 친구라면 B와 A도 친구다.

union find를 집합의 개수를 세면 풀 수 있다. 매우 쉬웠고 10분 정도만에 풀 수 있었다.

#include <iostream>
#include <cstring>

using namespace std;

int Answer;
int par[100005], lev[100005];

int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y) {
    int a = find(x), b = find(y);
    if (a == b) return;
    if (lev[a] > lev[b]) swap(a, b);
    par[a] = b;
    lev[b] += lev[a];
    lev[a] = 0;
}

int main(int argc, char** argv)
{
	int T, test_case;

	cin >> T;
	for(test_case = 0; test_case  < T; test_case++)
	{
		Answer = 0;
        int N; cin >> N;
        for (int i = 1; i <= N; i++) {
            par[i] = i;
            lev[i] = 1;
        }

        for (int i = 1; i <= N; i++) {
            int ipt; cin >> ipt;
            if (i + ipt <= N) merge(i, i + ipt);
        }

        for (int i = 1; i <= N; i++) {
            if (lev[i]) Answer++;
        }
		cout << "Case #" << test_case+1 << endl;
		cout << Answer << endl;
	}
}

2. 이진수

길이가 n인 이진수 A가 주어주고 정수 t가 주어지고 아래 규칙으로 새로운 이진수 B를 만든다.

1. 만약 i>t이고, ai−t = 1이면 bi = 1이다.

2. 그렇지 않고 i ≤ n−t이고, ai+t=1이면 bi=1이다.

3. else bi=0이다.

B와 t가 주어졌을 때, A를 복원해야 한다.

가능한 A가 여러 가지라면, 그중 가장 작은 것을 출력한다.

bi가 0이라면 bi-t, bi+t는 항상 0 이여야 하고, i <= t일 경우에 bi가 1이라면 ai+t는 1이고, bi가 0이라면 ai+t는 0이다. i + t > n인 경우는 bi가 1이라면 ai-t는 1이고, bi가 0이라면 ai-t는 0이다. 이것을 전처리해두고 나머지는 항상 더 작은 것으로 고르면 된다.

이 문제도 풀이는 금방 생각났지만 구현에서 약간 버벅거려서 시간을 조금 날렸다. 그리고 왜 그런진 모르겠는데 endl대신 "\n"을 사용했더니 계속해서 틀려서 endl으로 바꿨더니 맞았다.

#include <iostream>

using namespace std;

int arr[500005], ans[500005];
int flag[500005];

int main(int argc, char** argv)
{
	int T, test_case;

	cin >> T;
	for(test_case = 0; test_case  < T; test_case++)
	{
        int n, t; cin >> n >> t;
        for (int i = 1; i <= n; i++) {
            scanf("%1d", &arr[i]);
            flag[i] = 0;
            ans[i] = 0;
        }

        for (int i = 1; i <= n; i++) {
            if (i - t < 1 && i + t <= n) flag[i + t] = (arr[i] ? 1 : -1);
            if (i + t > n && i - t > 0) flag[i - t] = (arr[i] ? 1 : -1);
            else { 
                if (!arr[i] && i + t <= n && i - t > 0) flag[i + t] = flag[i - t] = -1; 
            }
        }

        for (int i = 1; i <= n; i++) if (flag[i] == 1) {
            ans[i] = 1;
        } 

        for (int i = t + 1; i <= n - t; i++) if (arr[i]) {
            if (i + t <= n && ans[i + t]) continue; 
            if (i - t <= n && ans[i - t]) continue; 
            if (i + t <= n && flag[i + t] == -1) ans[i - t] = 1;
            if (i - t > 0 && flag[i - t] == -1) ans[i + t] = 1;
            if (i + t <= n && i - t > 0 && flag[i + t] != -1 && flag[i - t] != -1) ans[i + t] = 1;
        }
        
		cout << "Case #" << test_case+1 << endl;
        for (int i = 1; i <= n; i++) cout << ans[i];
        cout << endl;
	}
}

_________________________________________________수정_________________________________________________

2솔이여서 1차에서 당연히 떨어졌을 줄 알았는데 통과했다.