티스토리 뷰

지난 9월 23일 acm-icpc 인터넷 예선을 치뤘다.

목표는 대학 순위 9등 전체 순위 20등이었는데

대학 순위 6등 전체 순위 15등으로 목표치보다 결과가 좋아서 기분이 좋다.


시간순으로 이벤트를 설명하자면

일단 시작하고 K 등록을 봤는데 작년에는 팀명 팀번호? 이었던거 같은데 비밀번호를 입력하라고 했다.ㅋㅋㅋㅋ

다행이 팀아디 비번 팀명 3개를 적어놔서 0분 솔브했다.


이후 한글 문제를 찾다가 H를 내가 읽었고 두 수에서 최댓값과 세 수 에서 최댓값을 구하는 문제이었다.

배열을 소팅하고 3개조합을 뽑는 포문을 짠다면 ijk 3중 포문을 돌릴텐데 사실 최대값이므로 k는 j+1이거나 n이어야 하는게

명확하다 위 방법으로 구현하였고 6분 솔브하였다. 조금만 더 빨리 풀었으면 퍼솔이었을텐데 아쉽다.


이후 팀원이 I를 할 수 있겠다고해서 넘겨줬고 12분 솔브하였다.

오늘 I를 읽었는데 행, 열로 최댓값 찾고 나머지 지우는 문제였다.


그사이 A문제를 읽었고, y값이 고정이므로 단순한 이분탐색문제인것같아 바로 구현하였고 17분 솔브하였다.

4문제 해결하는데 17분 걸렸고 스코어보드 거의 최상위에 있었다. 이제 쉬운문제는 끝난것 같다는 느낌이 직감적으로 있었고

J를 읽었다. (전~혀 감도 안오는 문자열 문제여서 바로 버렸다.)


남은 한글문제인 C, G와 영어 문제 E의 설명을 팀원들에게 들었다.

C는 정확히 문제를 이해하지 않았지만 구현문제인 것 같았고(사실 세줄 이상 읽는거 힘듬;;) 팀원에게 생각해보라고 넘겼다.

G도 이 때 문제를 들었을 때는 N을 10만으로 읽어서 그리디라고 생각했고 될만한걸로 한 번 시도해보고 다른문제 읽으라고하고 팀원에게 넘겼다.

E는 문제설명 듣자마자 그냥 기하+플로우 문제임을 알았고 자잘한 예외 케이스를 생각하는 동안 G를 팀원이 시도했고 틀렸다.


이후 내가 E를 잡고 구현했다. 예상 구현시간으로는 30분을 생각했는데 더 오래 걸려버렸다. 테스트 케이스 그림이 현실성이 없어서

안 보일거같은데 사실 다 보이는 (쥐-구멍) 테케였다. 디버깅하는데 헛시간을 썻고 ccw 한 군데에 long long이 아닌 int를 써서 틀린걸 찾는것도 시간이 걸렸다. 96분에 솔브하였다. (ACG팀이 퍼솔할때 사실 코딩이 끝나고 테스트케이스 디버깅하고 있었는데 이 시간만 줄였어도 흐으 아쉽다. 60~70분대로 풀었다면 더 괜찮은 성적이 나오지 않았을까 싶다.)


그다음 B,D,L의 문제 설명을 들었다. 스코어보드도 많이 쳐진 상황이었고 G가 다른팀들이 꽤 많이 시도 되었고 많은 팀들이 맞았으나 일단 머리속에서 그리디로 상상회로 돌린 상황이라서 이걸 잡으면 100%말린다는 확신이 있었다.

그래서 일단 C구현을 시키고 다른 문제를 고민해 보도록 했다. 다음 B는 직감적으로 그냥 걸렀고(그래프에 이렇게 심플한 문제는 논문일 거 같다는 느낌이 강했다.), D도 사실 비슷한 이유로 걸렀다.


그리고 L에 집중했는데 카이스트팀이 비교적 빠른 시간에 푼 점이랑 다른팀들 스코어보드를 관찰해보니 엄청 전형적인 문제일것 같다는 느낌이 컸다. FFT로 슥삭하는 문제인것 같았는데 합성곱 식이 도저히 떠오르지 않아서 긴가민가하면서 다른 풀이도 생각했다.

지금생각해보면 E를 풀고 1시간 24분의 시간이 있었는데 그 시간동안 뭘했는지 무슨 고민을 한건지 도통 모르겠다.ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

종료 20분쯤남았을때 합성곱식이 떠올랐고 코딩하고 슥삭하고 제출했다. 178분에 AC맞았다. 


전력 분석으로는 초반은 매우 좋았다 대전가서 모든 문제가 영어일 때도 이런 템포를 낼 수 있을지는 걱정이지만 일단은 쉬운문제 잘 찾고 빠르게 해결했다는 점에서 높게 평가한다.

문제는 중후반이라고 생각한다. 보통 상위권 스코어보드 보면서 많이 풀린 문제들 따라가는 식으로 해결하였는데 따라가는 입장에서 더이상 풀린 문제가 없었고 새로 잡아야 하는 상황이었다.

한글 문제가 보통 쉽다는 작년의 교훈으로 C,G가 중위권 문제라고 생각했고 팀원들에게 넘겼는데 해결되지 않아서 아쉽다.

의사소통에 있어서 테스트 케이스를 만들어 달라거나, upper_bound, lower_bound를 생각해달라고 부탁하는 적이 없어서 그 부분에서 협력이 아쉬웠고, 개인적으로는 아직 구현력이 부족한 것 같다. 더 노오오력 하면 될 것 같다.

FFT문제 같은 경우에는 이번이 FFT문제를 처음 풀어보긴 하는데 확실이 좀 풀어봤다면 더 빨리 합성곱식을 떠올릴 수 있었을 텐데 하고 아쉽다. F번은 문제도 읽지 않았는데 이것도 구현해본적은 없지만 충분히 할 수 있을만한 문제 였다고 생각한다. 


팀원들은 중위권 문제의 솔루션이 나올정도로 레벨업하고 나는 구현속도를 더 정확히 더 빨리 할 수 있도록 + 상위권 문제를 풀 수 있도록 노력해야 하겠다고 일단 생각했다. (나는 오렌지를 가고 팀원들은 퍼플을 보내면 해결!!)


이런 느낌으로 토요일을 보냈고, 안 푼 문제들에 대해서 입풀이를 적어보자면


B는 아직 생각 안 해봤다 


C는 사실 문제에서 요구하는 답은 항상 명확한 것 같다. 기존 그래프는 트리고 B하나당 순방향 엣지 하나 L하나당 역방향 엣지 하나씩 추가 된다.

그래서 정점과 간선수는 쉽게 구해지고 답은 바로 나온다. 이제 불가능한 경우만 배제하면 되는것 같은데 자아아아아알 예외 찾아서 하면 될거 같다.


D는 F1(x) = x를 루트로하는 서브트리에서 x를 찍고 나서 모든 서브트리 정점을 찍고 x의 자식중에 하나를 찍고 나오는 함수  F2(x) = x를 루트로 하는 서브트리에서 x의 자식중에 하나를 찍고 들어가서 모든 서브트리 정점을 찍고 x 를 찍고 나오는 함수 2개를 잘 조합하면 다 처리 할 수 있을 것 같다. 재귀함수로 불변식만 지켜가면서 번갈아 가면서 쓰고 종점 t가 있는 서브트리만 잘 예외처리하면 될거 같다.


F는 사실 왼쪽 볼록 껍질을 구하면 되는 건데 set이랑 lower_bound랑 파라매트릭 스까서 잘하면 선분 하나씩 추가해 가면서 볼록껍질을 완성한 set을 만들 수 있을 것 같고 여기서 그냥 쿼리만 해결하면 될 듯 하다.


G는 dp[i][j] = i번째 지점에 블록을 놓고자 할때 이전에 j번 위치에 j번블럭 우측하단을 놓은 경우로 정의하고 현재 i번 블록에 대해서 i번 지점을 우측하단으로 하게 놓을수 있는지? 아니면 j번위치로부터 붙여서 놓는경우로 나눠서 N^2 디피를 하면 될거 같다.


J도 생각 안 해봤다.


(입풀이 참교육 당해야 하므로 백준에 인예문제가 빨리 올라왔으면 좋겠다.)


대전에서 좋은 결과 있으면 좋겠다. 화이티이이이이ㅣㅇㅇ~~~~

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함