[210807] SCPC 2021 예선 2차 후기

예선 2차는 1차와 다르게 꽤나 어려웠다.

종료 30분 전 제출현황 사진.

일단 예선1차 통과라는 목표는 이루었기 때문에,

전투적으로 응시했다기보단 경험삼아 응시해보았다.

이게 바로 합리화인가...

 

1500점 만점에 100점의 점수를 획득하여 마무리지었다.

1번을 해결하고 2~4번을 보다가 엄두가 나지 않아 오전에 1, 3번 제출해보고, 저녁에 조금 더 건드려보다가 마무리지었다.

 

난이도가 꽤나 높아 포기하려는 마음이 강했는지, 문제 구경 위주로, 부담없이 쭉 훑어보고 끝냈다.

 

1번은 수학, 2번은 ???, 3번은 BFS, 4번은 KMP로 접근해보았다.

정확한 풀이가 나오면 한번 살펴봐야겠다.

---

1. 원 안의 점

간단한 수학문제였다. 

예선1차의 1번 문제보다도 쉽다.

원 안의 정수좌표점의 개수를 세는 문제이다. 적절한 예외처리를 해줘야되는데, 예외처리 또한 크게 어렵지 않아 거의 대부분은 쉽게 AC를 받았을 것이다.

이 문제의 정답자로 예선2차 진출자 명수를 파악하면 될듯하다.

// main함수만 올립니다.
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		ans = 0;
		cin >> R;
		ll n = R * R;
		for (ll i = 1; i < R; i++) {
			ll num = n - i * i;
			ll k = sqrt(num);
			ans += 2 * k + 1;
			if (k * k == num)
				ans -= 2;
		}
		ans *= 2;
		ans += 2 * (R - 1) + 1;
		cout << "Case #" << test_case + 1 << "\n";
		cout << ans << "\n";
	}
}

2. 직8각형

컨벡스헐이라 하기엔, 좌표를 이리저리 옮길 수 있다는 점이 걸리고, 

범위가 좀 커서 이분탐색을 생각해보기도 했는데 그렇다기엔 적절한 처리가 생각이 안나고.

브루트포스나 적절한 구현일 듯한데 딱히 풀이가 생각이 나지 않는다.

기하 문제일지 구현 문제일지 감이 안오는 문제.

200명 이상이 해결하였는데 아직 많이 모자란듯하다. 구현 위주의 문제들을 많이 풀어봐야겠다.

대회가 끝나면 다른 분들의 도움을 받아봐야겠다.

 

+) 백트래킹 + 수학인 듯한데, 크게 어렵지 않아 조금 아쉽긴 하다.

 

3. 산탄총

처음 떠올랐던 것은 BFS. 만점풀이는 도저히 생각나지 않아 N<=50일 때의 부분점수만이라도 긁으려고 BFS코드를 짜보았으나 0점. 테스트케이스 T가 최대 50이기 때문에 O(N^5), O(N^6) 풀이는 막히는 듯하다.

내가 생각한 풀이는 모든 점에서 BFS를 돌리고, 중심의 위치는 표적지 밖이 될 수도 있으니 k값도 1~K까지 달리하여 돌리되, 가장자리가 아닌 경우는 K일 때만 돌리는 방법을 사용하였다.

// main함수만 올립니다.
	for (test_case = 0; test_case < T; test_case++)
	{
		ans = 0;
		cin >> N >> K;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> a[i][j];
			}
		}
		for (ll i = 0; i < N; i++) {
			for (ll j = 0; j < N; j++) {
				for (ll k = 1; k <= K; k++) {
					ll num = min({ i, j, N - i - 1, N - j - 1 });
					if (num && k != K)
						continue;
					memset(visit, false, sizeof(visit));
					res = 0;
					bfs(j, i, k);
					ans = max(ans, res);
				}
			}
		}
		cout << "Case #" << test_case + 1 << "\n";
		cout << ans << "\n";
	}

 

4. 패턴매칭

내가 배우지 않은 알고리즘을 사용하는 것이 아닐까 의심이 드는 문제. 

맨처음 생각나는 것은 KMP의 fail함수였다.

문자열 T의 substring을 패턴 P의 길이만큼 fail함수를 만들어 패턴의 fail함수와 같으면 매칭 성공.

예제는 역시 제대로 나오나, O(N*K*테스트케이스 개수 24)여서 부분점수 테케조차도 1초의 시간 안에 해결되지 않아 0점.

 

+) KMP로 섭테를 긁을 수 있다는데 0점이 나온 이유가 무엇인지 고민해봐야겠다.

// main함수만 올립니다.
    for (test_case = 0; test_case < T; test_case++)
	{
		ans = 0;
		cin >> N >> K >> s;
		for (int i = 1; i <= K; i++) {
			int ret = 0;
			string p;
			cin >> p;
			if (p.length() == 1) {
				ans += i * N;
				continue;
			}
			vector<int> v2 = fail(p);
			for (int j = 0; j <= N - p.length(); j++) {
				vector<int> v1 = fail(s.substr(j, p.length()));
				if (v1 == v2)
					ret++;
			}
			ans += i * ret;
		}
		cout << "Case #" << test_case + 1 << "\n";
		cout << ans << "\n";
	}

 

5번은 아예 쳐다보지도 않았다.

---

일단 이번 SCPC의 목표는 예선 1차 통과였기 때문에 목표는 이루었다.

구현, 수학, 문자열 문제를 많이 해결해보고,

골드 상위 ~ 플레티넘 티어 문제들을 많이 연습해야겠다.

 

좋은 경험이었다.

다른 분들의 풀이를 보며 열심히 공부해야겠다.