SCPC 4회 1차 2차 예선 풀이

다 풀었다! ( 선형배치 빼고 ㅋㅋ )

곧 있으면 SCPC 2차 예선이라 4회 예선 문제들을 쭉 풀어보았습니다.

 

버스타기 회문인 수의 합은 풀려있어서 그 외에 것들을 다 풀어보았습니다.

 

1. 우주정거장

 

처음에 이 문제를 삼각형 개수 찾는 문제로 생각해버려서 혼자 삼각형 개수를 $ N * log N $ 만에 찾으려고 쌩쇼했던 기억이 납니다...

하지만 당연하게도 그렇게 푸는 것이 아니고 더 쉽게 풀 수 있습니다. ( 애초에 그게 답도 아니다 ㅋㅋ )

 

생각을 전환시켜서 제일 마지막에 만들어지는 $ X $ 를 생각해봅시다.

그럼 그 $ X $ 는 당연히 정점 두 개만 연결되어 있을 것입니다.

$ X $ 와 연결된 두 정점을 찾아봅시다.

그 두 개의 정점을 $ A $ $ B $ 라고 했을 때 $ A $ 와 $ B $ 가 연결이 되어있으면 $ X $ 를 지웁니다.

그럼 $ A $ $ B $ 각각 정점이 한 개씩 줄테고 이 두 정점도 정점이 2개씩만 연결되어있다면 위에 과정대로 쭉 해주면 됩니다.

 

$ O(N + M) $

 

2. 선형 배치

 

이 문제의 만점에 도전하는 사람은 정말 RESPECT 합니다.

전 포기했습니다 ㅎㅎㅎ 

168 점 받는 방법은 그냥 정점을 1 ~ N 까지 일렬로 나열한 뒤

$ N^{2} $ 에 어떤 두 정점 $ x $ 와 $ y $ 를 swap 했을 때 원래의 값보다 더 작아지면 바꿔주는 식으로 했습니다.

그럼 $ N $ 이 100 이고 각 정점에 연결되는 간선의 최대값이 30 이기 때문에 ( 20도 확률이 10 퍼센트입니다 )

이 과정을 2000번 정도 돌려줄 수 있습니다.

 

그럼 168.xxx 점수를 얻을 수 있습니다!!!

 

한 5시간정도 씨름을 해보았지만 168이란 숫자에 혐오증을 느끼는 병에 걸리기만 하고 진전은 없었습니다.

 

3. Lights to Stage

 

선형 배치를 5시간동안 풀다가 이 문제를 보고 힐링했습니다.

일단 문제에서 이분 탐색을 쓰라는 듯한 제스쳐를 굉장히 많이 풍깁니다.

이분 탐색을 안쓰고도 풀 수 있는 방법이 존재할 순 있지만 저는 쉬운 길을 좋아하기에 그러지 않았습니다 ㅎㅎ

 

 

$ y $ 가 $ X $ 이하인 곳에만 전등을 단다고 가정하겠습니다.

그럼 각 다각 선분마다 이 전등을 다는 위치가 정해집니다.

그럼 그 전등을 다는 위치에서 범위가 만들어지게 되고 이 범위가 $ M $ 개가 생깁니다.

즉 이 문제는 이 범위 $ M $ 개 중 $ L $ 개만 써서 $ 0 \sim  N $ 까지 범위를 포함할 수 있냐를 묻는 문제고

$ N $ 이 20만이다보니 포함할 수 있는 지를 $ O(M) $ 만에 풀어라고 우리에게 외치고 있습니다......

$ MlogM $ 이 허용됬더라면 참 행복하게 풀 수 있을텐데 우리에게 머리를 쓰라고 강요합니다..

생각을 해보면 기울기가 1 또는 -1 로 강제되어 있기 때문에 어떤 구간의 최대값이 그 다음 구간의 최대값을 넘지 못합니다.

즉 그리디하게 처음에 0을 포함하는 범위 중 최대값이 가장 큰 것을 선택해주고 그리고 그 최대값을 $ X $ 라고 했을 때 이 $ X $를 포함하는 범위 중 최대값이 가장 큰 것을 선택해주고... 이런 식으로 하면 최적임을 알 수 있습니다.

그렇게 했을 때 선택된 다각 선분의 개수가 $ L $ 보다 작은지 큰지를 판별하여 이분 탐색을 돌리면 됩니다.

 

$ O(NlogN) $

 

4. Quick Sort

 

저는 $ O(N) $ 의 풀이를 너무나도 찾고 싶었지만 제 뇌가 거부했습니다!!

그냥 set 써서 잘 돌리면 뚝딱 풀립니다. ( 갓.자.료.구.조 SET )

 

$ O(NlogN) $

 

5. 메모지

 

이 문제는 이해하는 것이 푸는 것보다 더 어려웠습니다!!

코드포스 대회에서도 문제 이해는 안되고 시간만 흘러가면 그보다 더 짜증나는 일이 없는데 제가 백수라서 다행이였습니다.

 

문제는 뭐 주렁주렁 달려있는데 그냥 정점의 y 값이 distinct 하고 그 정점과 연결된 메모장(?) 이 오른쪽에 있을 텐데 메모장을 안 겹치도록 잘 배치해서 정점에서 그 메모장으로 갈 때 선분의 꺾이는 개수를 최소화 시켜라가 문제입니다.

 

x 값은 그럼 왜 있냐구요? 저도 모르겠습니다. ( 이것 때문에 또 문제 잘못 이해했나 5분은 더 들여봤습니다. )

또 각 선분은 교차해서는 안됩니다. 

 

일단 이 문제는 $ N <=10^{4} $ 인거 보니 $ N^{2} $ 이 될 것만 같습니다. 

 

$ dp[X] $ 를 $ X $ 개의 꺾인 선분을 가질 때 $ y $ 의 최소값으로 정의합니다.

 

$ H[x] $ 는 $ x $ 번째 메모장의 높이 $ Y[x] $ 는 $ x $ 번째 정점의 $ y $ 값이라고 하겠습니다. 

 

1. $ dp[x] $ 가 $ Y[t] $ 보다 크면 $ dp[x+1] = min(dp[x+1],dp[x] + H[t]) $ 를 하면 됩니다.

2. 그게 아니라면 두 가지 경우가 생깁니다.

 2.1 $ dp[x] $ + $ H[t] $ 가 $ Y[t] $ 보다 클 때는 $ dp[x] = min(dp[x],max(Y[t],dp[x] + H[t])) $ 를 해줍니다.

 2.2 $ dp[x] $ + $ H[t] $ 가 $ Y[t] $ 보다 작을 때는 2.1에서 했던 것과  $ dp[x+1] = min(dp[x+1],dp[x] + H[t]) $ 를 해줍니다.

 

6. Bitonic Paths

 

이름부터 너무 멋있네요. 문제도 멋있습니다.

 

다익스트라를 돌려줍니다. 근데 다익스트라를 그냥 돌리면 당연히 WA 를 받습니다....

왜냐하면 어떤 정점에 최소로 도착했다 하더라고 바로 전 간선의 가중치에 따라 그 다음으로 갈 곳이 달라져버리기 때문이죠.

그럼 어떻게 다익스트라를 예쁘게 돌려야 될까요?

생각을 해보면 어떤 정점 $ X $ 에서 $ Y $ 로 갈 때 가중치 $ W $를 타고 갔다고 합시다.

그럼 $ X $ 에서 $ Y $ 로 갈 때 그 다음으로 최소인 값이 $ W $ 를 타고 가는 건 아무 의미가 없습니다. 왜냐하면 그 전에 최소로 간 값이랑 똑같은 루트를 타기 때문입니다.

즉 $ X $ 에서 $ Y $ 로 $ W $ 를 타고 갔으면 $ W $ 의 가중치는 지워줍니다.

이렇게 되면 간선의 갯수만큼 다익스트라를 돌게됩니다.

 

$ O((N+E)log(E)) $

 

7. 지진

 

맞왜맞!!

 

이 문제의 시간복잡도가 이해가 되지 않아 적어보았지만 제가 틀릴 수도 있습니다.

만약 알고 계신다면 댓글로 제 무지를 깨우쳐주시길 바랍니다.......

 

저는 이 문제를 $ N*M*logM $ 으로 풀었습니다.

$ N * M $ 으로 푸는 법을 2시간 정도 생각해봤는데 답이 없더라구요 그래서 그건 포기했습니다.

 

일단 패턴의 가중치를 $ 0 \sim M - 1 $ 로 상대적 순서를 비교해 바꿔줍니다.

그리고 각 $ N - M + 1 $ 구간마다 그 구간을 빼내서 상대적인 순서를 비교해 $ 0 \sim M - 1 $ 로 바꿔줍니다.

두 번째 구간은 동일한 값이 존재할 수도 있지만 동일한 값도 그냥 distinct 하게 바꿔줍니다.

즉 3 2 2 2 가 있으면 4 1 2 3 으로 바꿔주는 거죠 이렇게 바꿔주어도 상관은 없습니다.

 

그리고 첫 번째 구간의 각 원소와 두 번째 구간의 각 원소를 순서대로 pair 시켜줍니다.

그리고 pair의 첫 번째 원소 기준으로 오름차순 정렬을 시킵니다.

 

어차피 패턴은 상대적인 순서를 비교하기 때문에 원래의 구간에서의 위치는 크게 상관이 없습니다.

그래서 정렬을 시킬 수 있습니다.

 

그럼 우리는 $ dp[x] $ 를 x 번째를 무조건 사용한다고 했을 때 $ 0 \sim x - 1 $ 에서 버려줘야 하는 원소들의 개수라고 정의합니다.

그럼 $ dp[x] = \sum_{k = 1}^{x-1} if(arr[x] > arr[k]) $ $ min(dp[k] + (x - k - 1)) $ 가 됩니다.

이 식을 seg tree 써서 잘 돌려주면 됩니다.

 

$ O(N*MlogM) $

 

 

8. 히스토그램

 

우와 수학문제다!!!! 도망치자!! ....

 

이 문제는 정당성 증명 ? 문제라고 생각합니다.

 

$ \sum_{i\in I}^{} (H(i) - H'(i))^{2} $ 를 풀어내면

$ \sum_{i\in I}^{} H(i)^{2} - 2*H(i)*H'(i) + H'(i)^{2} $ 가 됩니다.

그럼 $ H(i)^{2} $ 는 필요없으니 제외 시킵니다.

그럼 $ -2*H(i)*H'(i) + H'(i)^{2} $ 남게 됩니다. ( 왜 여기는 라텍스 적용이 안되죠? )

어떤 구간 $ x \sim y $ 까지의 y 값을 하나의 값 $ R $ 로 줄인다고 가정하겠습니다.

그럼 $ x \sim y $ 의 히스토그램 y 값의 합을 $ K $ 라고 했을 때 

값은 $ -2*K*R + R^{2} * ( y - x + 1) $ 이 됩니다. 편의상 $ (y - x + 1) $ 을 T라고 하겠습니다.

그럼 여기서 최소값은 R 이 $ \frac{K}{T} $ 일 때가 됩니다.

그리고 그 최소값을 넣은 값은 $ -\frac{K^{2}}{T} $ 가 됩니다.

그러면 여기서 정당성 증명이 하나 더 생깁니다.

히스토그램이 증가한다고 했을 때 둘은 합쳐줘야 되는가? 라는 문제이죠

당연하다고 할 수 있겠지만 증명을 하게 되면은

$ \frac{x^{2}}{y} + \frac{a^{2}}{b} >= \frac{x^{2}+a^{2}}{y + b} $ 이런 식을 증명하면 됩니다.

그냥 풀어서 나열하면 된다는 것을 알 수 있습니다 ㅎㅎ ( 직접 해보세요!! )

즉 합치지 않는 것이 무조건 이득입니다.

 

그럼 이제 히스토그램을 $ x $ 가 증가하는 순서대로 보면서 이 정점이 그 전 히스토그램보다 크다면 스택에 추가해주고 그 전 히스토그램보다 작다면 합쳐주는 식으로 진행하면 됩니다.

 

끗!

 

4회 본선은 적을 진 모르겠으나 3회 예선 풀이도 적을 수 있으면 적을 예정입니다