티스토리 뷰

1. POI

디스크립션을 차근차근 읽으면서, 문제의 점수, 참가자의 점수, 참가자의 등수를 문제에 적혀있는 그대로 계산하면 됩니다. 


2. 내일 할 거야

문제를 쉽게 변형해서, 과제 리스트가 주어졌을 때 모든 과제를 마칠 수 있는지를 yes / no로 판별하는 문제를 생각해 봅시다. 이 경우 과제를 데드라인 순으로 정렬한 후 처리하는 그리디 알고리즘이 최선임을 증명할 수 있습니다. (데드라인이 큰 것을, 데드라인이 작은 것보다 먼저 처리할 이유가 없음) 

한편, T일 쉰다는 것은, 사실 모든 데드라인을 T일 앞당긴 후 과제를 시작한다는 것과 동치입니다. 고로 과제를 하는 순서가 바뀌지 않습니다. 실제 T를 구하는 것은 과제를 역순으로 보면서 할 수 있습니다.


3. Archery Tournament

원은 빠르게 다루기 극히 힘든 구조 중 하나입니다. 고로, 다른 단순한 구조를 생각하는 것이 좋습니다. 이 문제에서는, 원을 감싸고 좌표축에 평행한, 변의 길이가 $2y_i$이고 중심이 $(x_i,y_i)$ 인 정사각형을 생각해 볼 수 있습니다. 물론, 정사각형은 원보다 더 넓은 면적을 덮으니, 어떠한 점을 덮는 정사각형이 여러 개일 수 있고. 정사각형이 점을 포함한다고 실제 원이 정사각형을 포함하는 것도 아닙니다. 

다행히 이러한 문제를 해결할 수 있는 좋은 성질이 있습니다. y축에 평행한 선을 그었을 때, 이 선이 관통하는 정사각형이 많지 않다는 것입니다.

어떠한 y축에 평행한 선 ($x = 0$이라 합시다.) 을 지나는 원을 모두 생각해 봅시다. 우리는 이 중 중심이 $x \geq 0$에 있는 원의 개수를 세 볼 것입니다. 원들은 모두 겹치지 않기 때문에, 임의의 두 원 $(x_1,y_1)$ / $(x_2,y_2)$ 에 대해 $(x_2-x_1 )^2+(y_2-y_1 )^2 \geq (y_2+y_1 )^2$ 를 만족합니다. 이 때 $x_2 \leq y_2,x_1 \leq y_1$ 이니, 이와 함께 식을 전개하면 $y_2 \geq 3y_1$ 이나 $y_1 \geq 3y_2$  중 하나가 성립한다는 결론이 나옵니다. 즉, 넉넉히 잡아 $2 log_3(10^9)$ 이 겹치는 원의 개수의 상한입니다. (물론 실제로는 이보다 작습니다.)

결론에 의해, 대략 40개의 원만 보면 되고, 정사각형이 된다고 x좌표 범위가 달라지지 않으니 40개의 정사각형만 보면 됩니다. 그 40개는 어떻게 빠르게 찾을까요? 이제 y좌표를 무시하고 x좌표 기준으로 문제를 다시 해석해 봅시다. 

* $[x_i-y_i,x_i+y_i]$ 를 덮는 구간이 삽입 / 삭제 된다.
* $X = x_i$ 쿼리가 주어졌을 때, 당신은 이 점을 포함하는 구간을 아무거나 찾은 후 지워야 한다.

이는, 구간의 시작점을 key로 하고 끝점을 value로 하는 이진 트리를 만든 후, key $\leq x_i$ 인 구간에서 value를 최대화하는 원소를 찾고, 이 원소가 value $\geq x_i$를 가지면 제거하는 식으로 해결할 수 있습니다. 초기 입력을 받으면 좌표 압축을 통해 key를 $[1,N]$ 사이의 서로 다른 정수로 바꿀 수 있으니, 구간 최솟값을 구할 수 있는 아무 자료구조 (예를 들어 세그먼트 트리) 를 사용해서 문제를 해결하면 됩니다.


4. Broadcast Station

예전에 써 놓은 풀이의 링크를 걸어둡니다.


'공부' 카테고리의 다른 글

2018 KAIST RUN Spring Contest  (0) 2018.05.27
Proving the 5-color theorem  (2) 2018.05.11
RUN@KAIST 2018 겨울 3주차 연습 문제  (5) 2018.02.02
BOJ 내가 만든 문제집  (2) 2018.01.27
2018.01.23 problem solving  (2) 2018.01.23
RUN@KAIST 2018 겨울 2주차 연습 문제  (1) 2018.01.22
댓글
  • 프로필사진 귤덕 항상 잘 보고 있습니다. 그리고 감탄하고 좌절합니다... 저도 알고리즘 문제를 잘 풀고 싶은데 잘 안되네요..ㅠ 백준 문제를 단계별로 풀고 있는데 동적계획법에서 너무 느립니다.. 한문제당 어느정도 붙잡고 있어야 할까요 ㅠ 조언 부탁드립니다! 2018.02.04 21:09 신고
  • 프로필사진 구사과 안녕하세요. 답답한 마음 잘 이해하지만, 공부 방법이나 시간 분배는 사람마다 다른 것이라 제가 조언할 수 있는 내용이 아닙니다. 많이 해 보시고 본인에게 제일 적절한 전략을 택하시는 걸 권합니다.

    블로그 내용이 도움이 되셨다니 감사합니다.
    2018.02.05 15:30 신고
  • 프로필사진 gs15120 안녕하세요 경곽 후배입니다^^
    제가 코이 1100개 쯤 푸니까 더 이상은 풀 수 있는 문제가 없더라고요 ㅜㅜ
    위에 조언 할 수 없다고 하셨지만, 거의 1주일째 허둥대고 허둥대고 있다보니 비슷한 경험 있으시다면 그 이야기라도 좀 해주실 수 없을까요?

    2018.02.22 17:19 신고
  • 프로필사진 구사과 문제를 혼자서 도저히 풀 수 없다고 생각이 든다면, 풀이를 보고 푸는 방법을 익히는 것이 좋겠죠. 출처가 적힌 대다수의 문제들은 풀이를 찾을 수 있을 것입니다. 특히 올림피아드 문제들이 그렇습니다.

    더 공부하고 싶으시다면 코이스터디 이외의 온라인 저지에서 문제를 푸는 것도 좋습니다. 일반적으로 공부하기 좋다고 거론되는 문제 셋들은 USACO / COCI / AtCoder / CSAcademy 등이 있습니다. 모두 문제 질이 괜찮고 풀이를 제공하기 때문입니다. 앳코더는 http://kenkoooo.com/atcoder/ 를 사용하면 문제 풀이에 더 도움이 될 것 같습니다.
    2018.02.22 20:49 신고
  • 프로필사진 gs15120 감사합니다! 2018.02.22 23:01 신고
댓글쓰기 폼
공지사항
Total
124,475
Today
76
Yesterday
141