구사과

1. 레이저원점을 지나는 직선이 해당 선분을 맞추려면 기울기가 어떠한 수의 구간 사이에 있어야 한다. 그러니 2차원 평면에 직선을 쏴서 선분을 맞춘다고 생각하지 말고, 수직선에 구간이 있는데 점을 몇 개 넣어서 구간들을 덮는다고 생각해보자. 모든 점들이 1사분면 위에 있고 x/y축에 닿지도 않기 때문에, 각 구간은 어떠한 분수와 분수 사이의 폐구간으로 쉽게 표현할 수 있다. 하지만, 더 간단하게 분수가 아닌 정수로 생각해 줄 수도 있다. 각 분수의 정확한 값이 아닌 대소 관계만이 중요하기 때문이다. 고로 좌표 압축을 통해 분수를 적당한 0 - 2n-1 사이의 정수로 바꿀 수 있다. 이제, 0 ~ 2n-1 사이의 정수를 시작점 끝점으로 가지는 n개의 폐구간이 있을 때, k개의 실수를 골라서 최대의 구간을 ..

(5/1 16:53 초판)(5/4 LM 풀이 추가, RST 약간 수정)(8/14 크리님의 생일을 맞아서 다시 풀어보고 있다. YZ 풀이 추가. RST 풀이 약간 추가) 범수형이 검수하러 간 틈을 타서 몰래 껴들어갔다. 팀 이름은 내가 AcornCkiGs14004Team으로 지었다. 하지만 ainta가 지은 기만 팀명에 능욕당했다. 이럴 줄 알았으면 ↑우리보다못하는팀 으로 바꾸고 나올 걸 그랬다...아쉬움 없을 만큼 하고 나왔기 때문에 아주 즐거웠다. 사실 극후반부에 서버가 터져서 PQ 제출에 문제가 있었다. 열심히 제출해도 안 돼서 상당히 짜증났지만, 알고 보니 내 제출이 4시간 59분 59초에 기적적으로 큐에 들어가서 2점을 득점했었다 (...) 그래서 안 짜증났다. 후기는 그냥 좀 재미있던 것만 간략..

1. Fenced In (Platinum)독특한 형태의 그래프에서 최소 스패닝 트리를 구하는 문제이다. 일반적으로 최소 스패닝 트리는 크루스칼 알고리즘을 사용해서 해결하지만, 여기서 그러한 해결 방법을 택하면, 간선의 개수가 너무 커서 시간 제한을 초과하기 때문에, 더 좋은 아이디어가 필요하다.아이디어는 크루스칼 알고리즘과 동일하다. 최소 비용으로 합쳐줄 수 있다면 합쳐주는 식이다. 다만 이 때, 하나 하나 일일이 합쳐준다기 보다는 한꺼번에 한 행 / 열을 합쳐준다는 점을 주목할 필요가 있다. 같은 행 (내지는 열) 에서 좌우로 인접한 셀들을 합치는 비용은 모두 똑같기 때문에 한 번에 생각할 수 있기 때문이다. 한 행과 한 열을 한번에 처리해 주면, O(n+m) 개의 이벤트만이 존재하기 때문에 정렬 한번..