2022 SCPC 예선 후기

[1차 예선]

1차 예선은 커트라인이 널널하다는 사실을 알고 있어서 적당히만 풀었습니다. 풀이는 기억도 잘 나지 않을 뿐더러 잘 설명한 좋은 글들이 많기 때문에 생략하겠습니다.

 

[2차 예선]

그리고 오늘 2차 예선이 진행되었습니다. 대략적인 타임라인을 기술해보도록 하겠습니다.

 

~00:10

1번은 적당히 쉬운 것 같아서 바로 풀었습니다. 최소 횟수는 직관적으로 구할 수 있고, 비용 역시 k보다 작은 수가 등장하는 구간의 길이를 잘 관리해주면 구할 수 있습니다. 저는 pq+set을 사용했습니다.

 

~00:34

2번도 빠른 시간 내에 풀었습니다. 같은 반인 학생끼리는 가장 밖부터 묶어주는 것이 최적임을 알 수 있습니다. 이를 반복하면 여러 개의 구간을 얻을 수 있는데, 모든 구간의 길이의 합에서 겹치는 구간 쌍의 개수를 빼주면 됩니다. 그 이유는 겹치지 않으면 서로의 비용에 손해를 주지 않고 빼는 것이 가능하고, 이와 같은 관계가 DAG 형태이기 때문에 겹치는 경우만 고려해주면 다른 경우는 잘 빼줄 수 있습니다.

 

~02:03

이후 3번을 봤는데, 열심히 끄적이다가 K=0, 1, 2인 경우는 DP를 이용해 해결할 수 있다는 사실을 깨달았습니다. \(DP[i][j][k]\)를 \(i\)번 정점에서 알파벳 \(j\)인 간선을 골라야 하고, \(k\)번 스킵한 경우로 정의해주면 DAG 형태의 DP가 나옵니다. 만약 사이클이 생긴 경우 무한한 길이의 문자열을 만드는 것이 가능하다는 뜻이니 이를 잘 처리해주면 됩니다.

K가 무한인 경우 정점들을 SCC로 묶은 후 비슷하게 DP 식을 세워주면 됩니다. 이 때에 무한한 길이의 문자열이 생기는 조건은 한 SCC에 A, B, C인 간선이 모두 있는 경우입니다. 열심히 구현한 후, 2번정도 틀리고 AC를 받았습니다. 그 당시 C를 푼 사람이 9명밖에 없어 상당히 기분이 좋았던 것 같습니다.

 

~02:49

이후 4번을 봤는데, 마땅한 풀이가 떠오르지 않아 우선 62점을 긁기로 마음먹었습니다. 모든 직사각형에 대한 최대/최소를 전처리해주면 \(O(N^4)\)에 해결할 수 있습니다.

 

~06:23

이때까지는 4번과 5번을 번갈아 보았습니다. 5번은 73점짜리 섭태정도만 구해 놓은 상태였고, 4번은 도저히 모르겠어서 우선 73점을 긁었습니다.

 

~11:30

5-1을 긁은 이후 4번을 좀 봤지만, 모르겠어서 그냥 자고 일어났습니다. 그 후 대충 4번의 여러 사풀을 넣어보았으나 62점 이상의 결과를 얻을 수 없었습니다.

 

총점 100 + 150 + 200 + 62 + 73 = 585점으로 대회를 마무리했습니다. 솔브 수 보면 4번은 풀었어야 할 것 같은데 아쉽습니다. 또, 3번이 꽤 어려웠다고 생각했는데 푼 사람이 정말 많아서 놀랐습니다. 새삼 PS판이 정말 고였다는 점을 체감할 수 있었습니다. 본선을 갈 확률은 반반정도인 것 같습니다. 잘 풀려서 본선 후기도 쓸 수 있었으면 좋겠네요ㅎㅎ