본문 바로가기

Problem Solving102

2016 ACM ICPC Asia-Manila Regional 후기 12월 14일이 예비소집/등록이고 12월 15일이 본 대회였습니다. 12월 13일 오후에 공항에서 출발했습니다. 출국하는 날까지 기말고사와 텀 프로젝트를 하다가 와서 매우 피곤하였습니다. 마닐라 국제 공항에는 밤 10시 쯤에 도착했습니다. 숙소는 시험장인 Ateneo de Manila University에서 걸어서 5분 거리에 있는 Oracle Hotel & Residence 였습니다. 필리핀은 교통 체증이 매우 심해서 마닐라 국제공항에서 숙소까지의 거리는 차로 30분 거리 정도인데 실제로는 2시간 가까이 걸렸습니다. 마닐라 시 전체가 서울 도심과 같은 교통체증인데, 공항 근처는 특별히 더 심합니다. 기온은 20도 ~ 30도 사이였고, 조금 습하고 덥습니다. 자동차 매연 냄새가 정말 심합니다. 다음 날,.. 2016. 12. 16.
BOJ 13551 원과 쿼리 문제 링크 : https://www.acmicpc.net/problem/13551풀이 : 점들이 분포하는 영역을 정사각형 블록들로 나누어 생각해 볼 수 있다. 질문으로 어떤 원이 주어졌을 때에 정사각형 블록과 원의 공통된 부분이 있다면, 해당 블록에 속한 점들이 일일이 원에 속하는 지 확인하는 방법을 시도해 볼 수 있다. 원과 정사각형 블록과의 관계는 다음과 같이 크게 3가지로 나뉜다. 1. 원 내부에 정사각형 전부가 들어가는 경우 : 정사각형의 꼭짓점들이 모두 원에 속하는 것과 동치2. 원 외부에 정사각형 전부가 위치한 경우 : 원의 중심이 정사각형 외부에 있고, 정사각형의 각 변과 원의 중심과의 최소 거리가 반지름보다 모두 큰 것과 동치3. 이 외의 경우 : 해당 블록에 속한 점들과 원의 관계를 살펴.. 2016. 11. 17.
ACM ICPC 2016 본선 후기 대회 결과 : http://icpckorea.org/2016/REGIONAL/scoreboard.html 우리 팀은 Korea University 'Never Give Up'이다. 결과는 4th place 금상인데 비공식 등수는 전체 6등이다. 1,2,3등이 서울대, 4등이 KAIST, 5등이 National Taiwan University, 6등이 우리.우선, 원철이가 좋은 곳으로 숙소를 예약해주어서 엄청 편하게 대회 전날 잘 수 있었다. 여러모로 편하게 대회에 임할 수 있도록 많이 도와준 원철이에게 정말 고맙다. 5시간, 6시간 총 2번에 걸쳐서 11시간 숙면을 하고 아침을 간단히 먹고서 대회장으로 향했다.소음이 많아서 피곤해질까봐 가져온 귀마개를 쓰고 최대한 에너지를 아끼려고 노력했다.대회가 시작하.. 2016. 11. 5.
ACM ICPC 2016 인터넷 예선 E번 1. 한 다각형 P(k)를 어떤 선분 L(k)로 치환하는데 L(k)를 구성하는 두 점은, P(k)를 구성하는 점들 중 원점으로부터 각도 최소인 점과 최대인 점2. L들을 각도순으로 본다.2-1. L에서 선분의 시작이면, 힙에다가 해당 선분을 넣음.2-2. L에서 선분의 끝이면, 힙에서 해당 선분을 삭제함. 2-2-1. 힙의 중간 부분에 있는 원소이면, 힙의 마지막 원소랑 해당 번째랑 자리를 바꾸고, 올릴 수 있는 만큼 올리고, 내려갈 수 있는 만큼 내려보냄. 2-2-2. 힙의 끝에 있는 원소이면, 힙의 사이즈만 줄이면 됨. 어떤 단위 각도 구간에 대해서 원점에 가까운 선분 L1은 원점에 보다 먼 선분 L2보다 이후의 구간에서 계속 더 가까운 성질을 이용하면 된다. 이 성질이 성립하는 이유는 교차하는 선분.. 2016. 10. 1.
BAPC 2015 연습 결과 및 반성 대회 공식 스코어보드(BAPC 2015) 나는 A번과 K번을 풀고 Rikang형이랑 같이 J번을 해결했다. A는 Parametric Search + Greedy 였는데, Greedy 방법을 증명하고 코딩하느라 생각보다 시간이 오래 걸렸다. K번은 디오판토스 방정식을 활용하면 쉽게 풀 수 있는데, 계산식을 적다가 오타난 부분마저 그대로 옮겨 적었고 그걸 찾느라 많은 패널티를 받았다. 많이 아쉽다. 도중에 준식의 양변을 GCD로 나누는 부분이 있었는데, 결과는 변하지 않음에도 결과값에 GCD값을 곱하는 실수를 했다. GCD가 1이 아닌 예제만 하나 넣어보았어도 쉽게 찾을 수 있는 오류였다. J번은 해법 자체는 그렇게 어렵지 않은데, 최적화해서 TLE를 줄이는데 많은 공을 들였다. 어떻게든 해결할 수 있어서 .. 2016. 9. 24.

티스토리툴바