[Contest 1] SCPC 2021 Round 1 후기

🎈 Intro

대회 시간: 2021년 7월 16일 (금) 15:00 ~ 2021년 7월 17일 (토) 15:00

이 대회는 내가 태어나서 처음으로 참여해본 알고리즘 대회였다. 아직 알고리즘 공부를 시작한지 $3$주밖에 안 지났기 때문에 큰 기대는 하지 않고 문제를 훑어보기라도 해보자는 마인드로 대회에 참여하였다. 예상했던대로 $3, 4, 5$번은 손도 못대고 $2$번에서 막힌 채로 대회가 종료되었다.

7월 16일 기준으로 내 스펙은 다음과 같았다.

• solved 티어: 골드 $5$
• 푼 문제 수: $190$개
• 알고리즘 지식: 브루트 포스, 그리디, 분할 정복, DP + 2-1에 배운 자료구조 일부

---

🏆 결과

• [1번] 1번만에 성공 $(80/80)$
• [2번] 9번 제출하고 실패 $(0/150)$
• [3번] 시도 X $(0/180)$
• [4번] 시도 X $(0/190)$
• [5번] 시도 X $(0/200)$

---

1번: 친구들 (80/80)

처음엔 단순하게 배열로 접근할려고 생각했다. 근데 이 경우엔 뒤로 가는 방향까지 구현하려면 시간초과가 날 것 같아서 화살표를 양방향으로 연결시켜야겠다는 생각이 들었다. 이렇게 연결하고 보니 자료구조 시간에 배웠던 그래프처럼 생겨서 "연결 그래프의 개수"를 찾는 문제라는 것이 보였다. (백준 11724번: 연결 요소의 개수 문제 참고)

1. i번째로 입력한 숫자가 v라고 하면, 그래프에 간선 (i, i+v)을 대입한다.
2. 모든 정점에서 DFS로 방문하여 연결된 그래프의 개수를 구한다.

입력 예시: $1 \ 4\ 2\ 1\ 3\ 1$
출력: $2$

/*
You should use the standard input/output

in order to receive a score properly.

Do not use file input and output

Please be very careful.
*/

#include <iostream>
#include <vector>

using namespace std;

int Answer;

vector<vector<int>> edge;
vector<bool> visited;
int N;
int u, v;
int cnt = 0;

int dfs(int cur) {
	int result = 0;
	if (cur >= N) return 0;
	if (visited[cur]) return 0;
	visited[cur] = true;
	result++;
	for (int i = 0; i < edge[cur].size(); i++) {
		int there = edge[cur][i];
		if (there >= N) continue;
		if (visited[there]) continue;
		
		dfs(there);
	}
	return result;
}

int main(int argc, char** argv)
{
	int T, test_case;
	/*
	   The freopen function below opens input.txt file in read only mode, and afterward,
	   the program will read from input.txt file instead of standard(keyboard) input.
	   To test your program, you may save input data in input.txt file,
	   and use freopen function to read from the file when using cin function.
	   You may remove the comment symbols(//) in the below statement and use it.
	   Use #include<cstdio> or #include <stdio.h> to use the function in your program.
	   But before submission, you must remove the freopen function or rewrite comment symbols(//).
	 */

	 // freopen("input.txt", "r", stdin);

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		Answer = 0;
		/////////////////////////////////////////////////////////////////////////////////////////////
		cin >> N;
		edge.resize(N + 1);
		visited.resize(N + 1);
		for (int i = 0; i < N; i++) {
			cin >> v;
			edge[i].push_back(i + v);
			if (i+v < N)
				edge[i + v].push_back(i); // 양방향 그래프로 만들기
		}
		for (int i = 0; i < N; i++) {
			if (dfs(i) > 0) Answer++;
		}
		edge.clear();
		visited.clear();
		/////////////////////////////////////////////////////////////////////////////////////////////

		 // Print the answer to standard output(screen).
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;//Your program should return 0 on normal termination.
}

---

2번: 이진수 (0/150)

아직도 왜 틀렸는지 잘 모르겠다. 테스트 케이스도 $20$개 이상 실행해봤는데도 반례를 찾지 못했다.

1. A 초기화: A를 x로 가득찬 문자열 초기화한다.
2. 단방향 수열 결정하기: B에서 $0 \le i \lt t,\ n-t\le i \lt n$ 구간에 $1,\ 0$이 있으면 A[i+t] 또는 A[i-t] 자리에 $1,\ 0$을 대입한다.
3. $0$ 넣기: B의 가운데 부분에서 $0$이 있는 경우 A[i-t], A[i+t]에도 $0$이 존재해야 한다.
4. 나머지 사이 부분 결정하기: B에 $1$이 있는 경우, A가 최소가 되게끔 $1$과 $0$을 적절하게 대입하면 된다. 최대한 왼쪽에 $0$이 가고 오른쪽에 $1$이 가도록 대입해주었고, 이미 숫자가 존재하면 빈 자리에 $1$이나 $0$을 대입하였다.
5. 남은 부분 $0$으로 채우기: t가 n/2보다 큰 경우 가운데 부분이 빌수가 있다. 따라서 남은 공백은 모두 $0$으로 채워야 A가 최소가 된다.

✔ 2번 문제 테스트 케이스 모음 (#3 ~ #6은 내가 임의로 만든 세트)

Case	n, t	B (input)	A (output)
#1	5 1	00111	00011
#2	10 2	1111111000	0111100000
#3	8 3	01110101	00101110
#4	9 6	111000001	001000111
#5	7 1	1011010	0100100
#6	7 2	1111111	0011110

/*
You should use the standard input/output

in order to receive a score properly.

Do not use file input and output

Please be very careful.
*/

#include <iostream>

using namespace std;

string Answer;

int main(int argc, char** argv)
{
	int T, test_case;
	/*
	   The freopen function below opens input.txt file in read only mode, and afterward,
	   the program will read from input.txt file instead of standard(keyboard) input.
	   To test your program, you may save input data in input.txt file,
	   and use freopen function to read from the file when using cin function.
	   You may remove the comment symbols(//) in the below statement and use it.
	   Use #include<cstdio> or #include <stdio.h> to use the function in your program.
	   But before submission, you must remove the freopen function or rewrite comment symbols(//).
	 */

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{

		/////////////////////////////////////////////////////////////////////////////////////////////
		string A, B;
		int n, t;
		cin >> n >> t >> B;

		// Step 1. A 초기화 (초기 상태 A: xxxxxxxxxx)
		for (int i = 0; i < n; i++) {
			A += 'x';
		}
		//cout << "Step 1) 처음 A: " << A << endl;

		// Step 2. 단방향 수열 결정하기 
		// t가 n/2보다 클 때는 이거만 하면 끝
		for (int i = 0; i < t; i++) {
			if (i + t > n - 1) continue;
			if (B[i] == '1') {
				A[i + t] = '1';
			}
			else {
				A[i + t] = '0';
			}
		}
		for (int i = n - t; i < n; i++) {
			if (i - t < 0) continue;
			if (B[i] == '1') {
				A[i - t] = '1';
			}
			else {
				A[i - t] = '0';
			}
		}
		//cout << "Step 2) 단방향 끝부분 넣은 후 A: " << A << endl;

		// Step 3. 0 넣기
		for (int i = t; i <= n - t - 1; i++) {
			if (B[i] == '0') {
				if (A[i - t] == 'x') A[i - t] = '0';
				if (A[i + t] == 'x') A[i + t] = '0';
			}
		}

		//cout << "Step 3) 0 넣은 후 A: " << A << endl;
		// Step 4. 나머지 사이 부분 결정하기 (왼쪽에 1이 없으면 왼쪽 0, 오른쪽 1 / 이미 있으면 오른쪽 1)
		for (int i = t; i <= n - t - 1; i++) {
			if (B[i] == '1') {
				if (A[i - t] == 'x' && A[i + t] == 'x') { // 둘 다 아무것도 없으면
					A[i - t] = '0';
					A[i + t] = '1';
				}
				else if (A[i - t] == '0' && A[i + t] == 'x') {
					A[i + t] = '1';
				}
				else if (A[i - t] == 'x' && A[i + t] == '0') {
					A[i - t] = '1';
				}
				else if (A[i - t] == '1' && A[i + t] == 'x') {
					A[i + t] = '0';
				}
				else if (A[i - t] == 'x' && A[i + t] == '1') {
					A[i - t] = '0';
				}
			}
		}
		//cout << "Step 4) 사이 정한 후 A: " << A << endl;
		// 남은 부분 있으면 다 0으로 채우기
		for (int i = 0; i < n; i++) {
			if (A[i] == 'x') A[i] = '0';
		}
		Answer = A;
		/////////////////////////////////////////////////////////////////////////////////////////////

		// Print the answer to standard output(screen).
		cout << "Case #" << test_case + 1 << endl;
		for (int i = 0; i < n; i++) {
			cout << Answer[i] - '0';
		}
		cout << endl;
	}

	return 0;//Your program should return 0 on normal termination.
}