2023 성균관대학교 프로그래밍 경진대회 Open Contest
2023 성균관대학교 프로그래밍 경진대회 Open Contest
www.acmicpc.net
서론
무려 한 달 만에 포스팅한다.
A - 증가 배열 만들기
대각선 방향으로 채우면 된다.
00:02 AC
B - 토크나이저
단순 구현
00:10 AC
E - AB
Trie
00:23 WA
변수를 초기화하지 않아 쓰레기값이 들어 있었다.
00:25 AC
C - 마법박스
답은 항상 소수라는 점을 파악하면 이분 탐색이 가능해진다.
00:31 WA
출력 형식을 지키지 않았다.
00:33 AC
D - 벌레컷
수식을 잘 정리한 후 이분 탐색 또는 two pointer로 해결할 수 있다.
식 정리는 내가 제일 약한 부분인데 때문에 시간이 오래 걸렸다.
긴가민가한 상태에서 확신이 들지 않았는데 더 이상 시간을 소비할 수 없어서 그냥 제출하였다.
00:56 AC
F - 최소 트리 분할
가중치가 큰 정점부터 보면서 합쳐 나가면 된다.
합치는 과정은 Union-Find로 처리할 수 있다.
01:22 AC
dfs 풀이도 가능한데 Union-Find 풀이와는 다른 방식으로 접근한다.
두 풀이 모두 시도해보는 것을 권장한다.
G - 시험
어디서 본 듯한 문제였는데 18342번과 유사한 문제였다.
18342번의 11점 풀이와 동일한 방식으로 풀 수 있다.
양변에 sum(Qx)를 곱한 후 이분 탐색을 충분히 돌리면 된다.
구체적으로 다음과 같은 배열 A를 정의할 수 있다.
A[i] = P[i] - mid * Q[i];
각각의 mid에 대하여 A를 정의한 후 상위 K개의 값을 뽑아내면 된다.
01:36 AC
H - 점프
보자마자 떠오른 것은 LzSeg인데 시간 안에 돌아갈 지가 의문이었다.
특히 나의 구현이 상대적으로 느린 편이라 바로 시도하기가 꺼려졌다.
다른 풀이를 두 개 정도 생각해보았는데 모두 코딩까지 마친 후 반례를 발견하였다.
답이 전혀 안 보여서 할 수 없이 LzSeg 풀이를 시도하였다.
02:27 WA
02:31 WA
구현 과정에서 사소한 오류가 있었다.
02:34 AC
1000 ms 제한에 868 ms로 매우 빡빡하게 통과하였다.
나중에 알게 된 사실인데 지문에 매우 큰 오류가 있었다.
실수 좌표에서도 이동이 가능하다고 가정하면 대략 2배의 좌표를 고려해야 하므로 속도가 느려진다.
하지만 문제 설명과 달리 채점 데이터에는 실수 좌표에서 이동하는 데이터가 존재하지 않았다.
절반 이상의 AC 제출이 이를 고려하지 않아 다음과 같은 입력에서 잘못된 답을 출력하였다.
4 3
1 4 1
1 2 2
3 4 2
1 4 3
위치 2와 3 사이에서 점프하면 한 번의 점프로 3층에 도달할 수 있으므로 답은 1이 된다.
정수 좌표에서만 점프가 가능하다면 답은 2가 된다.
이 문제는 데이터 추가 대신 지문을 수정하는 것으로 해결될 예정이다.
나는 데이터 추가를 바랬는데 출제자님은 지문 수정을 택하셨다.
실수 좌표 이동이 가능해야 재밌는 문제가 될텐데 아쉽게 되었다.
I - 양궁 (not solved)
다각형 내부 판별은 O(N)이 소요된다고 알고 있어서 문제를 해결할 수 없었다.
대회 종료 후 알게 된 사실인데 볼록 다각형에서는 이분 탐색으로 O(log N)에 판별이 가능하다고 한다.
따라서 모든 convex hull을 구성한 후 각 query마다 이분 탐색으로 답을 구하면 된다.
이분 탐색 과정에서 또 다른 이분 탐색을 수행하므로 각 query의 시간 복잡도는 O((log N)^2)이 된다.
J - 정렬 (not solved)
연산 횟수 제한은 상당히 빡빡하며 에디토리얼에는 도움되지 않는 정보만 들어 있다.
나는 radix sort를 이용하였는데 연산 횟수 제한 때문에 매우 괴상한 방법으로 해결하였다.
원소들을 3개의 그룹으로 나누는데 각 원소를 평균 5/3회의 연산으로 처리하면 된다.
예를 들어 배열 A0에 다음과 같이 a, b, c 그룹의 원소가 3개씩 들어 있다고 가정하자.
a1 b1 c1 a2 b2 c2 a3 b3 c3
각 원소는 그룹에 따라 다음과 같이 처리할 수 있다.
- 그룹 a: RO 연산으로 맨 뒤로 보낸 후 마지막에 PP 연산으로 배열 A1로 옮긴다.
- 그룹 b: PP 연산으로 배열 A1로 옮긴다.
- 그룹 c: PP 연산으로 배열 A1로 옮긴 후 RO 연산으로 맨 뒤로 보낸다.
그룹 b에 속하는 원소는 1회의 연산으로 처리할 수 있으며 나머지 원소들은 2회의 연산을 요구한다.
따라서 평균 연산 횟수는 5/3회가 된다.
참고로 나의 풀이에서는 RRO 연산을 사용하지 않는다.
연산 수행 후 배열 A0은 비어 있으며 배열 A1은 다음과 같이 채워진다.
a3 a2 a1 b3 b2 b1 c1 c2 c3
각 그룹은 제대로 분할되었지만 그룹 a와 그룹 b는 원소의 순서가 뒤집혔다.
때문에 단순히 모듈러 결과를 바탕으로 그룹을 결정하면 잘못된 결과를 얻게 된다.
잘 관찰해보면 규칙이 보일 것이고 해당 규칙을 바탕으로 그룹을 결정하면 된다.
2023/10/27 추가
동일한 N에 대하여 radix sort의 결과는 동일하다는 사실을 이용하면 규칙을 구할 필요가 없다.
radix sort의 결과가 [2 1 0 5 4 3 6 7 8] 이라고 가정하자.
이를 이용하여 기존 원소의 번호를 재배정한 후 다시 radix sort를 돌리면 된다.
ex) [1 3 5 7 9 2 4 6 8] -> [2 0 4 6 8 1 5 3 7]
K - GCD와 K번째 쿼리 (not solved)
gcd + segment tree + binary search + mo's + sqrt decomposition 환장의 콜라보
자세한 설명은 생략한다.
pst 풀이나 2d seg 풀이도 가능하다고 하는데 전혀 알고 싶지 않다.
끝
끝