티스토리 뷰

카카오 코드 페스티벌 본선 쑤아리 질러ㅓㅓㅓㅓㅓㅓ예에ㅔㅔㅔㅔㅔㅔ


경기창조혁신어쩌구경제뭐센터에서 9월 9일에 했다. 판교를 처음 가봤는데 회사들이 다닥다다닥 붙어있었다.

신기해애ㅔ에에ㅔㅔㅔ


(카와이이ㅣㅣㅣㅣㅣㅣㅣ)


광주에서 9시 30분 고속버스를타고 부릉부릉 떠나서 1시쯤 성남에 도착해 셔틀버스타고 1시 20분쯤? 에 최종 도착했다.

생각보다 직원분들이 되게 많았다.


샌드위치 3개 정도 쿰척쿰척하고 대회장에 들어갔다.



이런 느낌으로 세팅해두었다. 14시부터 대회 시작인데 13시 40분 부터 입장했던거 같고 연애인들의 코드 페스티벌 격려? 응원? 영상을 틀어줬다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 뜬금 없었다.

약간 mbc에브리원 10주년 축하합니다 같은 느낌의 축하 영상느낌이었다.

정지훈 나왔을 때가 진짜 뜬금없어서... 제일 웃겼고  에이핑크는 진짜 예쁘당.. 맨 앞자리 였으면 찍었을텐데 아쉽다. 



이 안에 오늘 본선 문제가 들어있다!! 헠헠

3시간 동안 8문제를 해결해야 한다.  14시부터 골골골 풀었다. scpc만큼 크게 결과를 원하던 대회는 아니라서 편한 마음으로 봤다.

1~4번을 먼저 다 읽은 후 1 -> 2 -> 4 -> 3 순으로 해결하고 5~8을 읽고 5번을 잡았는데 못 풀었당~~~

대회 끝나고 다시 샌드위치랑 김밥이랑 치킨이랑 과일이랑 냠냠하면서 갓갓분들이랑 인사하고 다녔다.



스코어보드 공개 및 시상식이 제일 재미있었다. ㅋㅋㅋㅋㅋㅋ

icpc 대전 리저널스타일로 시상식을해서 맨 아래부터 하나씩 문제를 까면서 순위 변동확인하고 특별상 주는 식으로 진행하였다.

특별상 한개라도 받고 싶었는데ㅋㅋㅋㅋㅋㅋㅋ큐ㅠㅠㅠㅠㅠ 이런 상복이 없나보다 흐규흐규

최종 스코어보드 결과 31등 하였다.

입상 커트라인은 4문제 패널티로 갈렸고 5문제 깔끔하게 풀었으면 입상 확정이었다.


&& 초 간단하게 문제에 대한 이야기를 해보자면


1번은 카카오 프렌즈 8명에 대해서 문제에서 주어진 n개의 조건을 충족하게 일렬로 줄을서는 경우의 수를 구하는 문제였다. 3번 문제를 읽는 중에 풀이가 생각나서 3번까지 읽고 풀었다. 8!로 다 해보면된다.

 

2번은 그래프에서 시간 t당 위치가 주어지는데 여기서 불가능한 경우를 없애야 하는 문제였다. 처음 쭉 읽을 때는 행렬곱셈순서같은 N^3 디피를 생각했었는데 아니었고 현재 시간이랑 이전 위치 2개를 인자로 가져가는 디피로 해결하였다. 맨 처음과 맨 끝을 바꿀수 없다는 조건을 제대로 읽지 않아서 1~2번 틀렸었다.


3번은 사천성이었는데 처음에는 그냥 대충 읽고 어떻게 풀지 빼액 하면서 4번을 읽었다. 4번을 풀고 자세히 읽어보니 최대 한번만 꺾이면 되는 리틀 사천성이었다! 항상 A부터 가능한지 확인 하면 되고 확인할 때 처음에는 방향을 트는 횟수를 가지고 다익스트라를 돌렸는데 시간초과가 나왔고, 이후에 항상 그냥 한 문자쌍에 대해서 각각 상하좌우로 1을 쭉 밀었을때 2가 되는곳이 있으면 연결가능이고, 안되면 불가능이라는 식으로 체크하고 해결하였다.


4번은 형태는 n*m 디피였는데 생각해야 되는 인자가 한개 더 있었고 이게 범위가 2^31이었다. 하지만 좀 생각해보면 거리가 최대 n*m보다 커질수 없으므로 거리를 인자로 잡고 시간을 최소화 하는 문제로 바꾸면 된다. 다익스트라 돌렸다.


이렇게 4개풀고 50분 정도인가 남았다. 별로 시간이 안 지난거 같았는데 3번을 디버깅을 시작해버려서 꽤 시간이 빨리 흘러버린듯 하다.


그 다음 5, 6, 7, 8을 읽었다.


5번은 n*n 매트릭스에 k명을 상호간의 최대거리로 배치하는 문제였고 나머지 6,7,8을 읽은 후 이 문제가 가장 할만할 거 같아서 잡았다.

직감적으로는 비트마스크 디피나 플로우에 파라매트릭 섞으면 될거같다는 느낌은 있었는데 뚜렷한 솔루션이 안 보였고 그리디로 비벼볼까 하다가 너무나 많은 반례들이 생각나서 접었다.


6번이랑 7번이 각각 무슨 문제 였는지 햇갈리는데


귀걸이 문제는 여러 점이 주어지고 사각형을 만들 수 있는 방법이 있을때 경우의 수랑 그 중 어떤 한점이 추가되거나 삭제 되었을 때 경우의 수를 구하는 문제였다. 디피에 세그먼트트리를 섞거나 앞에서 부터 센 디피랑 뒤에서부터 센 디피 테이블 두개 가지고 비비거나 하면 될거같기도 했는데 이거를 50분안에 정확한 솔루션으로 구해서 못 풀거같아서 접었다.


그래프 문제는 어떤 조건을 만족하는 그래프 G에서 G'으로 변형이 항상가능하다고 증명이 이미 되었고 그럼 이 과정을 출력하는 문제였는데

대충 생각은 일단 갯수 맞게 켜고 사이클 구해서 이 안에서 막돌리면서 켜진 엣지를 전송하는 방식으로 어케어케 될거 같기도 했는데 생각을 그만 두었다.


8번은 킹갓 기하문제였고 

삼각형안에 n개의 점이 찍혀있고 삼각형에 고무줄이 달려있는데 각 삼각형 변에서 내부의 점들중 몇개를 선택해서 고무줄을 이용하여 3개의 컨벡스 헐을 만들었을 때 이게 서로 교차하지않게 컨벡스 헐을 만드는 경우의 수를 구하는 문제였다. 답을 출력하는데에 모듈라가 없는 걸로 보아 생각보다 크기가 작을것 같았고 잘 모르겠다~~


느낀점은 쉬운문제를 더 빠르게 풀어야 한다는 걸 알았고 어려운 문제도 많이 풀어봐야겠다~~

대충 앞으로 연습을 어떤식으로 해야할지 감이 잡혔다.

이제 올해는 LG대회, 샘숭SW테스트, icpc 대전리저널 3개 정도 남은 것 같은데 좋은 결과를 위해서 다시 달려보쟈~~

scpc이후로 너무 놀았자너ㅓㅓㅓ


&& 본선 전리품 &&



댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
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
글 보관함