RUN@KAIST 7/2 방학 연습 풀이

1. 점 고르기

모든 n^2개의 점을 잡아서, 두 점을 최대 / 최소로 하는 직사각형이 존재할 수 있는지를 판별하면 간단하게 풀 수 있다. 이 존재성은 단순한 O(1) 식으로 판단할 수 있어서, 시간 복잡도는 n^2이다. 난 n^2lgn에 풀었는데 내 풀이는 부끄러우니 설명을 생략한다...

2. Number Sets

P 이상의 모든 prime factor를 열거해야 할 것 같지만, 실제로 필요한 건 P 이상 1000000 이하의 prime factor 뿐이다. 1000001 이상의 prime factor는 중요하지 않은 게, B - A <= 1000000일 때, 두 수의 차가 1000001 이상인 쌍이 구간 [A, B]에서 있을 수 없기 때문이다.

이제 1000000개 이하 정도의 prime들을 돌면서 (에라토스테네스의 체로 전처리하자) 지금 보고 있는 prime factor x를 공유하는 숫자들을 같은 셋에 묶어줘야 한다. 다른 말로 하면 x의 배수들을 같은 셋에 묶어줘야 한다. 이는 union find 연산으로 구현할 수 있다. A 이상 B 이하의 x의 배수들을 모두 열거한 후 인접한 배수들끼리 union 연산을 해 주면 시간 제한 안에 풀 수 있다. 

3. Fairie's Sorcery 

준비중

4. 동전 뒤집기 3

일전에 포스팅했던 Jzzhu and Numbers 문제와 비슷한 타입의 DP를 사용해서 풀 수 있다. 아주 기막힌 문제였다.

입력으로 주어지는 숫자와, 행을 뒤집는 수열을 비트마스크로 표현하자. 만약에, 각각의 비트마스크 X에 대해서, 해당 비트마스크와 정확히 K개의 비트가 다른 숫자의 개수를 전부 알 수 있다면, Sum(min(K, N - K) * (K개의 비트가 다른 숫자 수)) 를 계산하면 O(NM)에 문제를 해결할 수 있다. 결국, "해당 비트마스크와 정확히 K개의 비트가 다른 숫자의 개수" 를 빠르게 구해야 하는데, naive하게는 O(M*2^N)의 시간이 걸려서 TLE가 난다.

이를 해결하기 위해서 DP를 사용하자, DP[i][j][k] = (입력으로 주어진 숫자들 중. j와 0 ~ i-1번째 비트들 중 정확히 k개의 비트가 다르고, i번째 ~ n-1번째 비트들이 j와 같은 수의 개수) 라고 정의하자. 일단 입력으로 주어진 M개의 비트마스크들만 가지고 DP[0][*][0] 를 채울 수 있다. 이제 순서대로 0 ~ N-1번째 비트들을 추가하면 문제가 풀린다. 상태 전이가 복잡할까? i-1번째 비트까지를 고려했을 때 i번째 비트를 추가하는 것은 아주 trivial하다! 설명을 하고 싶어도 할 수 없는 정도로 쉽다. 결국 DP 정의가 핵심인 문제다. 

시간 복잡도와 메모리 복잡도 모두 MN + N^2 * 2^N이지만, DP[i]를 보기 위해서 DP[i-1]의 값만 필요하므로, 메모리 복잡도를 N * 2^N으로 줄일 수 있다. 이렇게 하면 문제가 풀린다.