Codeforces Round 972 (Div. 2) 후기

스코어보드.

코포를 오랜만에 쳤다. 사실 오랜만에 쳤다고 하기에도 뭐한데, 코포 자체가 한 2주만에 열려서 그렇다.

추석이라 원래 환경 대신 가족들 있는 본가에서 쳐서 퍼포먼스가 좀 낮게 나와도 그러려니 하기로 했다.

 

최근 CP판에 AI 관련해서 issue가 좀 많은 것 같다.

이번 대회에서는 AI가 C와 E1을 모두 뚫었다고 한다. (근데 그 와중에 B2는 못 뚫었다...)

아무튼 AI 사용자들은 이긴 것 같아서 기분이 좋다.

 

딱히 앞에 쓸 내용이 없어서, 바로 본론으로 들어가겠다.

 

 

 

A (00:03)

맨 처음에 문제를 잘못 읽고 이웃한 애들끼리만 카운트된다고 생각해서, 'aeiou'등을 반복하는 제출을 했다 틀렸다.

이후 문제를 다시 읽고 'aaa...eee...iii... ...'을 냈고, 맞았다.

1틀을 했지만 예제를 틀려버려서 노카운트였다.

 

 

 

B2 (00:09)

B1 = B2 = 500이어서, 상위 문제인 B2를 먼저 읽었다.

대충 distinct하다길래 이탐하면 될 것 같았고, 실제로 이탐하니 맞았다.

 

 

 

B1 (00:10)

B2 맞는 거 보고 바로 냈다. 이거 맞은 시점에 rated 19등이었다.

 

 

 

C (00:38, +2)

쉬워 보이는 DP 문제였지만...

 

말았다. 구현상에 오류는 없었는데, 로직에 오류가 있었다.

로직을 세 번 고치고야 맞았고, 이거 말고 나서 대회 망했다는 생각이 들었다.

 

 

 

E1 (01:13)

처음에는 생각이 안 나서 고민하다, 시/공복도 O(LNM) 풀이를 떠올렸다.

근데 내가 사용하는 언어가 파이썬이라, 공간복잡도 O(LNM)이면 MLE가 날 것 같았고,

시간복잡도는 상수가 큰 O(LNM)이라 터질 것 같았다. 파이썬은 상수가 크면 O(3*10^7)도 보장하지 못한다.

 

하지만 다른 풀이가 생각나지 않아 구현해 봤는데, 신기하게도 구현상 오류 없이 바로 예제가 돌았다.

일단 TLE도 MLE도 날 것 같은 코드였지만, 다른 풀이가 전혀 생각나지 않아 제출해 보았다.

 

놀랍게도 시간도 메모리도 생각보다 훨씬 적게 돌았다.

나중에 사유를 알고 보니, 문제에서 의미없다고 생각한 x <= 7의 조건이, L을 7로 bound시켜 준다고 한다.

즉, 사실은 O(LNM)이 아니라 O(7NM)인 코드였던 것이다.

 

결국 PBA긴 했지만, 맞았으니 기분은 좋았다.

 

 

 

System Testing

평소에는 시스텟을 별로 신경쓰지 않았지만, 이번 시스텟은 좀 특별했다.

내 친구 리스트에 등록된 사람들이다. C가 아주 많이 터졌다.

C가 굉장히 많이 터졌기 때문이다.

 

나중에 알고 보니, 내가 푼 풀이/정해는 O(5NM)이었는데, 문제 조건에서 NM에는 제한을 뒀지만 N^2에는 제한을 두지 않아 O(N^2) 풀이가 모두 터졌다고 한다. (이 경우 최악 연산 횟수는 O(1e9)였다)

근데 또 신기한 건 내 위에 사람들은 별로 안 터져서, 내 순위는 2위밖에 안 올랐다. (151 -> 149)

 

랭킹보드에 누가봐도 AI 쓴 제출들이 좀 보이던데, 이것들 잘리면 순위가 더 오를 수도 있겠다는 생각이 들었지만 이대로 마무리되었다.

 

 

 

맺는말

여기 문단 제목 뭘로 해야 할지 모르겠어서 그냥 맺는말이라고 적었다.

 

이제 오렌지까지는 45점이 남았고, 곧 갈 수 있기를 희망한다.

내 CP의 마지막 목표가 오렌지라고 생각했는데, 생각보다는 빠르게 달성할 것 같아서, CP를 조금 더 열심히 파볼까 한다.