대회후기: SCPC 2022 Round 1

군대 사지방에서 짬내서 열심히 긁은 예선.

중간에 점호받으러 가고... 폰으로 보고.. 외출도 나가면서 디버깅 할 시간이 많이 부족했다.

특히나 익숙하지 않은 C++을 써야해서 디버깅이 너무나도 오래 걸렸다.

라운드 2가 걱정된다.

 

현재 더 이상 문제들을 열람할 수가 없어서 기억에 의거해 상당히 대충 작성하는 후기가 될 예정이다.

 

1. 개미

개미들을 stable sort하면 된다.

 

2. K 등분

맞웨틀.

총합을 k등분 한 값을 기준으로, k의 정수배인 지점들은 potential split point들이다.

DP 느낌으로, 이러한 potential point마다, 그 위치보다 앞서 온 split point까지의 경우의 수를 다 더해주면 된다.

사실 코드 다시 열어보기도 싫어서 설명도 대충 했다. 끝까지 점수가 10점밖에 안나왔다.

 

3. 직교 다각형

직관이 곧 정답이었던 문제. 문제에 예시로 주어진 그림을 잘 보면, 모든 가로줄과 세로줄에 대해, point를 하나 지나칠 때마다 line이 toggle된다. 이 사실에서 추가적으로 알 수 있는 insight는, 모든 가로줄과 세로줄에는 짝수개의 point가 있어야 한다는 점이다. 따라서 error point는 홀수개의 point가 있는 가로/세로줄의 교차 지점으로 찾으면 된다.

길이는 앞서 말한 toggle logic으로 구하면 된다.

 

4. 지우개

풀었는데... 구현할 시간이 부족했다.

a와 b 각각 기준, 바깥에 노출되지 않은 부분을 core라고 한다면, 이 core부분은 바뀔 수 없다.

Core가 매치되는 부분을 잘(예를 들어 KMP로) 찾아준 이후, core의 좌우로 충분한 개수의 a와 b가 있는지 확인해주려고 했다. 디버깅을 다 못끝내고 제출했다.

 

군대라서 이정도로 한 거라고 하자...

본선 제발..!