2023 ICPC 인터넷 예선 후기

본선에 참가할 순 없지만 심심해서 인터넷 예선에 참가하였다.

팀원은 andremjk1(휴학생)과 yjinpark

andrewmjk1은 나랑 원래 잘 알고 있던 사이고, yjinpark 님은 이번에 누가 추천해줘서 같이 팀을 했다.

일단 우리팀의 경과를 쭉 쓰고, 불평을 좀 늘어놔야겠다.

 

andrewmjk1은 문제를 출력하러 가고 yjinpark 님과 먼저 문제를 보기 시작했다.

전통적으로 한글 문제들은 쉬우니 먼저 보았다.

 

C. Happy Point

 

간단한 문제. yjinpark 님께서 먼저 문제를 읽었기에 구현을 시작하셨다.

여러 문제가 발생하였고, 이 때문에 내가 함께 구현에 관여하고 디버깅을 하였다.

1) C++를 쓰는 많은 사람이 헷갈려하는 getline이 필요한 문제였다.

2) 소수점 2번째 자리에서 반올림하여 출력하여야 한다.

1st WA) 우리의 소수점 2번째 자리 출력이 1.08이 아니라 1.8 을 출력하고 있음을 확인하였다.

2nd WA) Happy point와 Gloomy point에 대한 결과 출력이 50.00이 아니라 50을 출력하고 있음을 발견하였다.

-> 위의 과정 하나하나를 찾는 것이 상당히 긴 시간을 끌었다.

 

D. Palindrome Numbers

 

아주 간단한 문제이다.

사실 N이 10^(2e5)여도 풀 수 있겠지만 쉬운 문제로 낸 것 같다.

내가 먼저 읽고 가볍게 풀었다. 

 

G. Reafy 수열

 

솔직히 말해서, Reafy 수열이 다 해봤자 길이가 1e7이 안되기 때문에 걍 대충 해도 통과할 것이라 믿었다.

sort하고서 k번째를 출력하는 코드가 TLE를 받아왔다...

 

K. Symmetry of Stars

 

내가 G의 TLE 코드를 내는 동안 yjinpark 님이 푸셨다.

아주 단순한 코드를 냈는데 TLE

2초짜리 O(N^2lgN)을 냈는데 TLE라니... 어이가 없었다.

 

이거도 pair을 이용한 map이 느린가해서 조금의 최적화를 했다.

내 기본 세팅이 #define int long long이기에 이걸 풀고 제출했는데 여전히 TLE

 

그래서 최적화를 하나 더 하였다 => 대칭이라는 특성을 이용해서 계산을 1/2로 줄이는 방법이 있다.

이렇게 제출하니까 드디어 AC

 

G. Reafy 수열

 

vector의 sort가 너무 느렸나? 싶어서 이번에는 priority queue를 사용하는 코드를 짰다.

복잡도가 이론적으로 비슷하긴 한데 O(N^2lg(N^2))과 O(N^2lgN) 정도의 차이라서 일단 제출해봤는데 TLE

 

그래서 결국 선형복잡도의 코드를 짰다. -> Stack을 이용하여 O(|R(N)|)으로 수열을 construct하는 코드를 짰다.

이렇게 해서 결국 AC를 받았다.

 

ㅡㅡㅡㅡㅡ 이쯤이 90분 정도 시점이고 잠시 스코어보드를 보았다. ㅡㅡㅡㅡ

=> 대충 I > J > A로 풀림을 확인할 수 있었으며, E는 풀 수 있는데 풀기 싫었다. (모두가 안 푸는 중)

=> 모든 문제를 읽고 있던 andrewmjk1이 A는 풀 수 없어보인다고 이야기하였다.

 

J. Server Overload

 

andrewmjk1에게 문제 설명을 듣고 내가 J를 바로 풀 수 있을 거라 생각해서 고민하기 시작했다.

문제를 읽으면 대충 각 줄마다 access count의 개수 x에 대해서 얻을 수 있는 최대합 dp[x]를 구해야 함을 알 수 있다.

근데 이게 Naive DP를 돌면 O(N^2K)인데 그건 될리가 없다고 andrewmjk1가 이야기했고 나는 동의했다.

 

하지만 조금 더 고민해보니 실제로 각 줄에 있을 수 있는 최대 개수 k = N / 3이기에 O(N^2k)이고 이건 됨을 직관했다.

근거는

1) 일단 이거보다 줄이는 방법이 쉬운 문제 레벨에서 없을거고

2) K를 k = N / 3으로 줄이는 것은 충분히 획기적인 trick이라고 생각하였기 때문이다.

그래서 이 다음에 K개의 합을 구하는 거도 O(NKk) 정도의 나이브한 코드를 짜서 제출했는데 TLE

심지어 구현 이슈로 WA도 받았던 것 같다.

 

I. Safari

 

내가 J에서 진흙탕을 만드는 동안 (사실 G, K에서 TLE를 받아보고서도 3e8이 J는 뚫릴 거라 믿는 건 좀 이상하긴 하다)

andrewmjk1과 yjinpark 님이 동시에 같은 관찰을 이야기해줘서 이걸 받아들였다.

[L, R]인 사파리에 도착하면 R까지 기다리는게 이득이라는 관찰인데, 내가 너무 의심이 많았나보다.

andrewmjk1이 관찰만 하고 구현에 대한 무언가가 없어보여서 내가 구현을 잡았다.

모든 사파리는 R 시점에서 나가므로, dp[i] = {i번 사파리에 R[i] 시점에 있을 때 최대 구경치}

진짜 내 기준에서 개깔끔하게 구현을 해서 제출했는데 WA.

 

J. Server Overload

 

현재 내 복잡도는 O(N^2k + NKk)이다.

앞쪽은 줄일 수 없다고 생각했고, 정해임을 확신했기 때문에 뒤쪽의 복잡도를 줄이기로 했다.

dp[i]가 위로 볼록한 곡선임을 알아차리고 priority queue를 이용하여 항상 최대의 증가치를 그리디하게 뽑았다.

구현 미스가 나서 WA를 받고, 끝나기 15분쯤 전에 AC.

 

I. Safari

 

평소에 dp를 만들면 초기값을 -INF로 잡을텐데, 갑자기 무슨 바람이 들어 0으로 잡아가지고 고생한 느낌이다.

아무튼 dp 초기값을 0으로 잡아가지고 실제로 방문하지 못한 사파리를 마치 방문한 것으로 착각하였다.

예를 들어 i번 지점의 택시 거리가 R[i]보다 크다면 R[i] 시점까지 절대 도달 불가능하므로 dp[i] = -INF로 해야했다.

이 부분을 상당히 늦게 발견하여 끝나기 20분쯤 전에 AC.

 

///

진짜 6솔 못했으면 너무 쪽팔릴거 같아서 후반에는 열심히 좀 했다.

초반부터 여러번의 WA, TLE를 받아서 (총 +12의 패널티) 조금 짜증이 많이 났다.

 

C 같은 문제는 내가 정말 싫어하지만, 뭐 이런 스타일의 문제는 여러 셋을 돌면 흔하디 흔하니 그럴 수 있다.

K는 O(N^2)이 의도라면 N = 5000이나 그 이상을 거는게 나았을 것 같다.

-> 개인적으로 풀이 흐름이 동일한데 구현의 차이로 TLE를 받은 느낌이라서 마음에 들지 않는다.

-> 우리가 O(N^2lgN)을 억지로 뚫은 것이라고 하면 할 말은 없다! 

G도 비슷한 이유로 마음에 들지 않는다. N을 굳이 5000으로 주었어야 하는가?

-> 심지어 이 문제는 nth_element으로 되기에 O(|R(N)| lgN)을 막았어야 했나 싶다...

J의 N값이 좀 애매하다는 생각이 들었다. 그냥 깡 O(N^3 + N^2K)도 뚫린다는 이야기가 있더라...

-> 솔직히 O(N^3 + KlgN)도 정해가 아닌 거 같고 NK 범위에 정해가 있는 것 같더라... 

A는 지문이 병신이라고 한다. 뭐 난 읽지도 않았으니 별 상관은 없다.

E는 관찰 따위 없는 깡구현 기하. 3시간짜리 대회에 재미도 없고 감동도 없고 시간도 없고

 

불평을 길게 늘어놨는데 이건 나 자신의 성장에 도움이 되지 않으니 다시 복기를 해보았다.

요새 문제를 많이 풀지 않아서 (해봐야 며칠에 한 번 플다 문제 하나씩) 구현 실력이 많이 느려졌고 잘 꼬였다.

이건 학교 공부(유급 위기)로 인한 현상이자 동시에 나의 방향성이 조금 바뀌었기 때문이다.

만일 기존 OReO에 있었으면, 어차피 쉬운 문제는 hibye1217 + junseo가 해주었을 것이다.

또한 코포도 지금 2550점인데 만일 점수를 올리려면 '1문제 더 풀기'를 해야 할거 같아서 어려운 문제에 집중했다.

단순히 플다만 푸는게 아니라 P54321 밀기도 조금 연습해야하나 싶다.

 

함께 팀 해준 andrewmjk1, yjinpark님께 감사드립니다.