ps 일기 (NYPC 1519 본선 진출!)

소녀 가극 레뷰 스타라이트 보세요.

 

저번 글을 쓰고 한달 정도가 되서 그동안 뭘 했는지 좀 적어볼까 한다.

 

일단 풀었던 인상깊은 문제들을 정리해보자면.. (개인 정리용이라 풀이가 엄밀하거나 자세하지 않음은 양해 부탁드립니다)

https://www.acmicpc.net/problem/19239

19239번: min-xor

집합에 원소를 추가하는 쿼리, 삭제하는 쿼리 그리고 집합에서 원소 2개를 골라서 xor 했을 때의 최소를 출력하는 쿼리가 들어온다.

xor의 최소는 수들을 오름차순 정렬했을 때 인접한 수들의 xor 값만 확인해주면 된다. xor이 최소가 되려면 두 수가 이진법으로 나타내었을 때 유사해야 하는데, 이는 정렬해주면 된다. 엄밀하게 증명을 하려면 $a \leq b \leq c$일 때 $a \oplus b \leq a \oplus c$ 임을 보이면 될 것 같은데 모르겠다(...) 추가) 트라이에서의 전위 순회가 오름차순 정렬과 같음으로 보일 수 있다. 그럼 이제 쿼리에서 주어지는 수들을 오름차순 정렬한 상태로 관리해주면 되는데, 그냥 bbst, 우선순위큐 같은걸 써주면 된다. 난 우선순위큐를 썼다. 여담으로 구현이 좀 많이 귀찮다. 오프라인 동적 연결성을 하면서 트라이를 관리해주면서 풀 수도 있다는데.. 이 제한으론 안된다고 한다.

 

https://www.acmicpc.net/problem/26105

26105번: Folding Stick

제목 그대로 막대를 부스지 않고 접어야 하는데, 그 때 막대 길이의 최소를 출력하는 문제이다.

재밌는? dp 문제였다. $sum(i)$를 i까지의 누적합, $dp(i) = i$에서 접었을 때 최소 길이 같이 정의해주면, i에서 접었을 때의 길이가 $dp(i) + s(i)$가 된다. 그럼 누적합이 저거보다 큰 i부터 이 dp값을 사용해줄 수 있고, 이는 이분탐색이나 우선순위 큐 등을 사용해주면 된다.

 

https://www.acmicpc.net/problem/3090

3090번: 차이를 최소로

수열의 원소를 1만큼 감소시키는 연산을 최대 T번 할 수 있을 때, 인접한 두 수의 차이 최댓값의 최소에 대한 문제이다.

최대의 최소? 너무 파라매트릭 같다. 인접한 수의 차이를 $X$로 줄일 수 있나? 에 대한 결정문제를 풀어주면 되는데, 이는 문제에서 주어진 연산이 수를 감소시키는 연산 밖에 없다는 점을 생각하면, 수열에서 가장 작은 원소와 인접한 원소들을 봐주면 됨을 알 수 있다. 이는 우선순위 큐 등으로 구현할 수 있다.

 

https://www.acmicpc.net/problem/8203

8203번: Lollipop

원소가 1, 2밖에 없는 수열이 주어진다. 그리고 부분합이 k인 부분합이 존재하는지, 존재하면 그 부분합을 출력하는 쿼리가 들어온다.

재밌는 수학 + 애드혹 문제다. 

std::lower_bound로 k이상의 누적합을 찾아주자. 그 값이 정확히 k면 그냥 1, index 를 출력해주면 된다. 아니라면 여기서 1을 빼주면 되는데.. 1, 2의 인덱스들을 따로 배열에 모아주고 거기서 이분탐색과 많조분을 열심히 하면 된다. 케웍이 좀 귀찮아서 쓰기도 귀찮다(....)

 

https://www.acmicpc.net/problem/28402

28402번: 두 트리

트리 2개와 각 정점에 대응되는 수열이 주어진다. 거기서 각 정점 i를 루트로 하는 서브트리에 대하여, 두 트리에서의 교집합 중 수열 값의 최대를 구하면 된다.

 

듣기론 classical data structure problem 이라고 하는데 실제 대회에서 퍼솔이 빠르게 나온걸 생각해보면 그런 것 같기도 하다. 풀이는 각 트리를 오일러 투어로 펼치면 2d RMQ 문제가 되는데, 분할정복을 하든 머지소트 트리를 쓰던 스몰투라지하면서 동적 세그를 쓰던 원하는 방법으로 구해주면 된다.

 

https://www.acmicpc.net/problem/24617

24617번: Redistributing Gifts

그래프 모델링이 굉장히 재밌는 문제였다. 각 소에 대해 선물을 바꿀 의향이 있는 소에게만 간선을 이어주고, 연결 여부를 따지면 된다. dfs를 하든 플로이드를 돌리던..

 

https://www.acmicpc.net/problem/18317

18317번: Farmer John Solves 3SUM

3 sum problem을 수열의 구간에 대해 푸는 문제이다. 3 sum problem은 수열의 세 원소에 대해 더해서 0이 되는 원소의 개수를 세는 문제이다. 

다양한 방법이 존재하는 것 같은데, 나는 세그 스위핑을 했다. 일반적으로 3 sum problem을 풀 땐 두 원소를 잡고, map등을 사용해서 그 원소의 합 * -1인 원소가 배열에 몇개 존재하는지를 확인해주는 방식으로 풀 수 있다. 이 방법을 응용하여, 구간 [l, r]에 포함되는 원소들만 map에 업데이트 해주고 -(a[l] + a[r])의 개수를 세주면 된다. 각 쿼리는 그 구간에 해당하는 구간들의 값의 합이 된다. 뭔가 설명이 좀 많이 이상한데 아마 대충 알아들었을 거라 믿는다(...) 이는 세그 등을 활용해서 스위핑 해주면 된다. 여담으로 제한이 구데기라 map이 아니라 bool 배열같은걸로 체크해줘야 한다.

 

 

https://www.acmicpc.net/problem/1762

1762번: 평면그래프와 삼각형

그래프에서 길이 3인 사이클의 개수를 세주는 문제이다. 그래프에서 모든 사이클 찾기는 np-hard 인걸로 알고 있어 이는 쉽지 않아 보인다. 정점 u, v에 대해, u - v인 간선이 존재한다 하면, u와 인접한 정점들과 v와 인접한 정점들의 교집합의 개수를 세주면 될 것 같다. 허나 이는 최악의 경우 제곱이 나올 수 있다. 그렇다면 인접한 정점들을 std::set 등을 사용해 저장해주고, 차수가 더 작은 정점을 기준으로 확인해주면 어떻게 될까? 그래도 뭔가 제곱 같지만.. 사실 이는 놀랍게도 $O(N\sqrt{N}\log N)$ 이다. 오일러 정리에 의해 평면 그래프에서 간선의 개수는 $O(정점의 개수)$ 임을 인지하자. 사실 간선이 최대 30만개라 이걸 몰라도 되긴 한다. 두 정점의 차수의 최소가 루트보다 작은 경우는 $O(N\sqrt{N})$에 계산해줄 수 있고, 최소가 루트보다 큰 경우엔 $O(N \log N)$이지만 이러한 정점의 개수는 루트보다 많지 않다.

 

https://www.acmicpc.net/problem/14898

14898번: 서로 다른 수와 쿼리 2

제목 그대로 수열에서 서로 다른 수의 개수를 세주는 쿼리가 들어오는 문제이다. 다만 온라인으로 풀어야한다. mo's 같은 걸 못쓰니 상당히 어려워보이는데.. 이 문제를 푸는 아이디어는 생각보다 간단하다. 수를 세줄 때 중복을 세주지 않으면 된다. p[i] = 수열에서 a[i]가 전에 나온 인덱스 중 최대 (존재하지 않으면 0) 을 정의해주면, 구간 [l, r]에서 p[i] < l인 원소의 개수를 세주는 문제가 된다. 이는 pst나 머지소트트리 등을 사용해서 풀어주면 된다. 

 

https://www.acmicpc.net/problem/26613

26613번: 수열과 구간과 구간과 구간과 쿼리

수열의 평균에 대한 웰노운 아이디어를 알면 쉽게 풀 수 있다.

k개의 평균을 $X$라 하면 $\frac{ \sum_{i = 1}^{k} a_{i} }{k} \geq X$, $\sum_{i = 1}^{k} a_{i} - X * k \geq 0$, $\sum_{i = 1}^{k} (a_{i} - X) \geq 0$ 가 된다. 쿼리에서 주어지는 [b, c] 사이의 합은 동일하기에, b로 끝나는, c로 시작하는 누적합의 최대를 찾아주고 만약 그 합이 0보다 크다면, 그 평균값은 valid 한 값이 될 것이다. 이분탐색으로 최대를 찾아줄 수 있다. 그럼 [a, b]에서 b로 끝나는 누적합의 최대를 찾아주면 되는데... 이는 식을 좀 정리해보면 일차함수 꼴이 나오고, 이제 세그에 리차오 등을 관리해주면 된다.

 

https://www.acmicpc.net/problem/26969#

26969번: Bribing Friends

생각을 많이 해야하는 문제이다. 네제곱 냅색은 자명하다. 이제 시복을 줄여보자.

친구 몇명을 데려간다 했을 때, $X_{i}$를 쓸 때 가장 이득은 작은 값부터 써주는 것이다. 그렇다면 $X$에 대해 정렬해주면 세제곱 정도에 풀 수 있다. 이제 관찰이 하나 더 필요한데, 최적해는 $B$만 쓰다 더이상 쓸 수 없을 때 $A$만 쓰기가 될 것이다. 그럼 이제 각 값을 dp로 잘 관리해주면 된다.

 

문제 정리는 이제 충분한 것 같고.. 어떻게 살았는가?에 대해 정리해보자면..

 

 

nypc는 운좋게 round2-B에서 379점을 얻어 본선에 진출하게 되었다! 본선 떨어지면 내 ps 인생은 여기서 끝이라 (적어도 졸업할 때 까진 수능도 있어서 추가적인 대회에 나가기 힘들다) 좀 많이 걱정했는데, 다행히도 운이 좋았다. nypc 얘기를 하고 싶지만 대회 규칙 때문에 풀이를 작성할 수 없어 본선이 끝나면 작성해볼까 한다.

 

대충 적어보자면...

round1은 그냥 200점만 받고 더 안풀었다. 뭔가 귀찮기도 해서..

 

round2-A는 완전 말아먹었는데, 그 당시 자존감도 완전 바닥에 수면 부족으로 피곤하고.. 여러가지가 겹쳐서 174점을 받았었다. 정신적으로 이상해서 대회를 완전 말아먹었는데, 끝나고 나서 문제를 다시 보니 전부다 내가 풀 수 있을만한 문제들이었고, 400점을 충분히 받을 수 있었을 거라는 근거 없는 자신감이 들었다. 그래서 round2-B에서는 정신을 차리고, 뇌절을 하지 않으며 잠을 충분히 자서 컨디션 관리를 하면 충분히 본선에 갈 수 있을 거라는 생각을 했다. 

 

round2-B는 전략을 어느정도 세웠는데...

1. 모든 문제를 적어도 30분은 고민해보기

2. 모든 문제를 고민해본 후 각 문제에 대한 기댓값을 대충 계산해보고 섭태/풀태 긁기

3. 나는 풀 수 있다 라는 마인드로 풀기

 

그래서 1, 2번을 봤는데 생각보다 너무 쉬워서 10분? 20분? 정도에 풀었던 것 같다. 그 후 3번을 봤는데... 구현이 좀 으으으으 여서 좀 말리다 결국 풀태를 먹었다. 이때 시간이 얼마 지나지 않아 상당히 기분이 좋았고 자신감도 들었다. 4번을 봤는데 식을 좀 정리해보니 자명하게 뭔가가 보여서 구현해보니 79점을 긁을 수 있었다. 간단한 최적화를 조금 더 추가하였으면 100점을 충분히 받을만 했었어서 아쉽긴 하다.

결국 전략은 아무 의미가 없었다(....) 그냥 자신감이 최고라 생각한다. 그래야 안말리는듯...

 

뭐 그래서 nypc 본선까지 2달 정도 남았다. 다음 달부턴 동아리 수업이 오프라인으로 돌아간다고 들어서, 동아리 수업의 도움을 받으며 좀 빡세게 준비해야겠다.