구사과

1. 워크스테이션 배정그리디 알고리즘으로 해결할 수 있다. 모든 배정을 시작점 순으로 정렬하자. i번 배정을 할 때, 만약에 이미 끝난 다른 배정 중, 끝난 시간과 현재 시간과의 M 이하인 것이 있다면 그 배정과 같은 워크스테이션을 쓴다고 생각하자. 만약에 그러한 배정이 여럿 있다면 차이를 최대화 하는 것이 이득이다. (차이를 괜히 작게 줘 봤자 시작점이 큰 다른 배정에게 도움이 안 되니까) 이러한 그리디 알고리즘을 priority queue 등으로 구현하면 O(nlgn)에 문제를 해결할 수 있다. 2. Identifying Map Tiles주어진 문자열을 비트마스크로 읽어서 출력하면 되는 단순 구현 문제이다. (사실 1번 2번은 일단 placeholder로 넣은 거였습니다. 즉 나중에 다른 문제로 고칠..

1. Kralj원형 구조에서 푸는 문제들은 그대로 풀면 짜증나거나 어려운 경우들이 많기 때문에 선형 구조로 환원시키는 것이 중요하다. 이 문제에서도 그러한 것이 가능하다. 어떠한 자리 i에 대해서, 어떤 몬스터들은 그 자리에 앉기 위해 달려들 것이고, 어떤 몬스터들은 그 자리에 실제로 앉을 것이다. flux(i) = (i번째 자리에 앉으려고 온 몬스터의 수) - 1이라고 하자. 1은 그 자리에 실제로 앉아서 싸우는 몬스터를 뜻한다. flux(i)의 부분합을 한번 그래프로 그려보자. 0점에서 올라갔다 내려갔다 했다가 다시 0점으로 오게 될 것이다. 이 중 최소를 찍는 위치가 있는데, 여기를 중심으로 왼쪽과 오른쪽 구간을 바꿔보자 (cyclic shift). 그렇다면, 이 그래프는 0점에서 올라가다가 내려가..

1. 점 고르기모든 n^2개의 점을 잡아서, 두 점을 최대 / 최소로 하는 직사각형이 존재할 수 있는지를 판별하면 간단하게 풀 수 있다. 이 존재성은 단순한 O(1) 식으로 판단할 수 있어서, 시간 복잡도는 n^2이다. 난 n^2lgn에 풀었는데 내 풀이는 부끄러우니 설명을 생략한다... 2. Number SetsP 이상의 모든 prime factor를 열거해야 할 것 같지만, 실제로 필요한 건 P 이상 1000000 이하의 prime factor 뿐이다. 1000001 이상의 prime factor는 중요하지 않은 게, B - A