와 icpc!
전역하고 처음으로 출전하는 icpc다. 군대에 있으면서도 대회를 나가고 싶어서 예선 본선 나올 때 마다 사지방에서 문제를 풀었는데 드디어 돌아왔다.
팀은 skeep194, hamuim, jsh00325 세 명 다들 열심히 해 줘서 5문제를 풀 수 있었다. 스코어보드 프리즈 전에 17등이었는데 그 후로 하나도 못풀어서 아마 20 초반 등수를 받았을 것 같다.
우리 팀은 매주 화요일마다 학교 앞 카페에서 모여 연습했는데 다들 할 수록 더 잘 하는 것 같아서 이번 icpc는 기대해볼만 하다고도 생각했다. 다들 연습에만 몰두한 나머지 대회 전날에서야 대회 칠 장소를 안 정했다는 사실을 깨달았고 급하게 주변 스터디카페를 빌렸다..
예선 결과로 학교 1등을 달성해서 본선 진출은 확정되었다. Team Hobanwoo 본선에서도 화이팅!!!
풀이
C
별 거 없는 제일 쉬운 문제였다. 지문에 나온대로 각 문자를 돌면서 HAPPY에 포함되는 문자의 개수를 세고 SAD에 포함되는 문자의 개수를 세주고 문제에서 주어진 식을 대입하면 정답.
D
부터 까지 정수 중 팰린드롬이 되는 수의 개수를 구하는 문제였다. 처음에는 digit dp인가 해서 넘기려고 했는데 N제한이 작아서 까지 보면서 반대로 쓴 숫자를 붙여버리면 무조건 팰린드롬이니까 그렇게 세줬다.
G
이번 icpc 예선 중 가장 억까가 심한 문제 아니었나 싶다. 한국어 번역이 있는 문제는 쉽다라는 국룰에 따라 단순히 분모 분자 쌍을 다 만들어서 정렬 후 번째 원소를 출력했는데 시간 초과가 났다.
번째 원소를 구하는 quick select라는 알고리즘의 존재는 알고 있었지만 팀 노트에 적어가지도 않았고 구현 자신도 없어서 일단 넘어갔다. C++라이브러리 함수 중 nth_element의 존재도 알고 있었지만 사용방법을 몰랐다...
그러던 중 어떻게든 상수 최적화를 해보겠다고 역수로 생각해서 0.1단위로 버킷 하나를 만들어서 버킷 하나만 정렬했더니 맞았다.
이번 기회에 nth_element 사용법이라도 알아놔야겠다..
void nth_element(arr.begin(), k, arr.end(), compare_func);//arr.begin()에서 arr.end()범위에서 k번째 원소를 arr[k]로 만든다.//비교함수는 정렬할 때 사용했던 거랑 똑같이 넣어준다.
K
좌표평면 상 점이 있는데 한 점을 잡았을 때 그 점이 두 점의 중점이 된다면 그 지점에 카운팅을 하고 가장 카운팅이 많은 지점의 카운팅 개수를 구하는 문제였다.
이거 그냥 별 다른거 없이 문제에 나온대로 중점잡고 카운팅해주는 브루트포스 하면 된다. 끝.
I
좌표평면 위에 개의 점이 있고 점은 특정 시간 구간에만 볼 수 있는데 점끼리 이동하면서 점을 가장 많이 구경할 때 몇 시간 동안 구경할 수 있는지 구하는 문제였다.
처음에는 시작 시간을 기준으로 그리디를 하는건지 끝점 기준으로 그리디를 하는건지 아니면 거리 순으로 봐야 하는건지 해서 시간도 2개고 좌표도 2개고 머리도 어지럽고 어려워서 던지려고 했는데 생각보다 많은 팀이 풀어서 다시 생각해봤다.
- 한 점을 보고있을 때 그 점을 끝나는 시간까지 보는게 무조건 이득이다. 중간에 다른 점으로 가는 경우 어차피 거기서 1시간 더 보나 전에 1시간 더 보나 똑같기 때문이다.
- 1번 사실을 이용해 점을 끝나는 시간으로 정렬 후 를 번째 점까지 사용했을 때 최댓값이라고 정의한다. 이렇게 하면 번째 원소에서의 시간은 번 점의 끝나는 시간이라고 생각해도 된다.
- 는 구간을 보면서 번째 원소에서 왔다고 가정했을 때의 구경 시간+의 최댓값을 구해준다.
- profit!!
결론
이렇게 5문제를 풀었고 나머지 문제랑은 열심히 눈싸움했다. J, A도 생각보다 해볼만한 문제였던 것 같은데 대회장에서 못푼건 조금 아쉬웠다.
본선까지 더 열심히 해야겠다.