SCPC 2022 본선 후기

- 참고: SCPC 2022 2차예선 후기 및 풀이

 

총 156..? 진짜 개같이 망했다.

목차
1. 총평
2. 후기
3. 풀이
4. 결론

---

1. 총평

좀 온사이트로 쳐 열지...

굳이굳이 온라인으로 여는게 참..

하지만 돈주는건 삼성이니 참도록 하죠

 

온라인 임을 감안했는지 문제들이 모두 능지문제로 구성되어 있다.

문제 선별은 보통 대회 한참 전에 이루어지는데, 그럼 그때부터 그냥 온라인 대회를 가정했다는 뜻이다.

그래서 그냥 돈도 아낄겸 온라인 가죠? <-- 된 상황 같다.

 

특이한 점은 배점이 모두 100점이고, 문제별로 난이도 차이가 뚜렷히 나는지 잘 모르겠다. (싹다 어려워서)

그리고 부분점수는 이것저것 많이 써놓으셨지만 실제로 긁을만한 것은 거의 없다시피 했다.

애초에 문제 성향상 0 or AC 스러운 것들이라 어쩔 수 없긴 하다만 좀 화가 난다.

 

또한 원래 내던 문제 유형에서 완전히 벗어나서, "긁기 힘든" 순수 능지 문제들로만 구성되어 있다는 점이 큰 충격이었다.

2차 예선이 복선이었을 줄은... 정말 몰랐다.

내년 SCPC 대비하는 사람들은 머리 꽤나 아플 것 같다.

 

올해는 SCPC를 딱히 대비하지 않아서, 전날에도 긴장이 전혀 없었고 큰일났음을 직감했다.

그래서인지 문제들한테 멘탈 박살나고, 아직까지 쉽사리 회복이 안되고 있다.

작년에 상 못받아놨으면 진짜 큰일날 뻔 했다.

 

2. 후기

1번 불일치도

- 냈더니 틀려서 소수점 오차 이슈인 줄 알고 똥꼬쇼를 벌였지만, 그냥 예외처리 이슈였다.

 

2번 돌무더기 게임

- $N^3$ DP는 10초만에 구상되지만, 이를 $N^2$으로 줄이는 관찰을 해야만 했다.

- 이런 문제들은 적절한 그리디 같은 풀이로는 절대절대 못 푸는 문제임을 알고 있었다.

- 그런데 어떻게 줄여야 할지 감이 안와서, 뒷 문제부터 보기로 했다.

 

3번 K등분 2

- 진짜 능지문제의 정수

- 혹은 전형적인 코드포스 문제 라고도 볼 수 있다.

- 몇십분 잡아봤지만 떠오르지 않아서 패스

 

4번 아름다운 수열

- 3번보다 더 코드포스에 가까운 문제다 ㅋㅋㅋ

- 무지성 풀이를 내봤는데 틀려서, brute-force로 stress 돌려봤다.

- 얘는 (정해를 봐야 겠지만) 짜증나는 예외처리 문제 같았다.

- 일단은 4번을 좀 파기로 했다.

 

5번 최적 함수

- 얘는 긁는것도 힘들 것 같아서 읽자마자 Pass함

 

이후:

4번에서 똥꼬쇼 몇 번 하다가 안되길래 3번으로 다시 가서 좀 고민했다.

 

문제 지문의 의도상 모든 가짓수를 만들 수 있다는 것 같은데, 이게 어떻게 만들어도 곱은 쉬운데 합을 사용하기 어렵다.

그래서 X가 소수가 주어지면 그냥 답이 없다.

 

이 문제 또한 끝까지 해결 못할 것 같아서, 9점만 긁고 그냥 다시 4번에 꼬라박기로 했다.

4번은 brute-force로 stress 만들어놓은 것도 있겠다 검증도 빡세게 할 수 있었다.

이게 모든 원소가 2개 이상이면 무조건 group을 지어서 +-+- ... -+-+ 이런식으로 배치하는게 무조건 좋다고 생각했었는데,

아래에 있는 그룹 하나를 한개씩 쪼개가지고 아래에 똑 똑 똑 놔주면 -2 씩 될 것이 -1씩만 되기 때문에 이게 더 좋다.

그런데 하나씩 쪼갠 것들이 남아버리면 말짱 도루묵이라서, 이런 경우에는 안쪼개는게 낫다.

이게 정해일 지는 모르겠는데, 아무튼 이렇게 짜고 stress도 잘 나와서 냈는데 틀렸다.

멘탈 팍 터지고 끝남

3. 풀이..?

푼 게 없어서 풀이를 쓸 수가 없다.

1번. 불일치도

count(L, R)을 누적 개수로 풀어서 쓴 다음, 인덱스 i에 관하여 묶으면 된다.

그럼 M = f(R)- f(L) 꼴의 식이 나온다.

R을 기준으로, f(R)은 고정되어 있으므로 0...R-1 에 대하여 f(x)의 최소값을 가지고 있으면 된다.

 

문제는 M이 양수일 때 나올 수도 있지만 음수일 때 나올 수도 있다.

따라서 무지성으로 for문을 두 번 돌려주면 된다.

 

다만 음수 계산할 경우 f(i) 식이 조금 다르게 나오기 때문에, 디테일을 조심할 필요가 있다.

시간복잡도: O(NlgN) (정렬 때문에)

2번. 돌무더기 게임

dp[i][j] = i번째 ~ j번째 무더기가 있고 A의 차례일 때 정답

dp[i][j] = min ( dp[i][k-1] , dp[k+1][j] ) + arr[k] 들의 최대값

 

이러면 $N^3$을 야무지게 긁을 수 있다.

나는 이걸 $N^2$으로 긁을 수 있는 방법에 대해 듣도 보도 못하여 포기했다.

 

누군가에 따르면, j가 고정되어 있을 때 dp[i][j] > dp[i+1][j] > ... > dp[j][j] = arr[j] 라는 사실을 이용하면,

k가 증가할 때 dp[i][k-1]은 증가하고 dp[k+1][j]는 감소하기 때문에 둘이 교차하는 지점이 최적해라고 한다.

 

arr[k]를 더해야 하는 부분은 dp배열 2개 더 만들어서 left[i][j] = arr[i] + dp[i][j], right[i][j] = dp[i][j] + arr[j] 뭐 이렇게 하면 그만이다.

교차하는 지점은 이분탐색 등으로 찾을 수 있을 것 같다.

시간복잡도: $O(N^2\log N)$

3번~5번

못풀어서 쓸 풀이가 없음

 

4. 결론

내가 못 봤기 때문에 질이 좋지 못한 아주 나쁜 그런 대회라고 할 수 있다.

SCPC 마지막 기회라서 상금 좀 타갈라고 했더니만, 개같이 멸망해 버려서 아쉽다. (화난다.)

페널티도 매우 커서 5등상 턱걸이조차 꿈도 꿀 수 없다. ㅂㅂ