RUN@KAIST 8/16 방학 연습 풀이

1. 지뢰찾기

디스크립션에 매우 중요한 내용이 누락되어 있는데, 외곽선만 숫자가 공개되어 있으며 외곽선이 아닌 부분은 숫자가 전혀 써져있지 않다. 고로 외곽선과 붙어있는 영역에만 지뢰가 있을 수도 없을 수도 있는 것이고, 그렇지 않은 n-4 * n-4 영역에는 지뢰가 무조건 있다고 가정해도 된다. 최대화가 목표이기 때문이다. 

외곽선과 붙어있는 영역의 지뢰를 최대화하라고 하지만, 사실 지뢰의 개수를 유일하게 결정할 수 있다. 모서리에 있는 지뢰를 제외한 모든 지뢰는 주위 3개의 셀에게 노출된다. 즉 모서리 지뢰를 제거하면 나머지 지뢰의 수는 적혀있는 숫자의 합 / 3 이라는 것이다. 모서리에 있는 지뢰는 모서리에 있는 숫자로 존재 여부를 결정할 수 있으니, 이를 결정하고 나머지 숫자의 합을 세주면 된다. n <= 4인 케이스를 조심하자.

2. Not So Random

그대로 기댓값을 찾는다고 생각하면 어렵지만, 주어지는 모든 연산이 비트 연산이기 때문에 각각의 비트가 독립적이다. 고로 각 비트의 기댓값을 따로 계산해 준 후, 기댓값의 선형성을 사용해서 다 더해주어도 무방하다. 

하나의 비트에 대한 기댓값을 구하게 되면, x와 k가 0 아니면 1이라고 생각할 수 있기 때문에 문제가 훨씬 쉬워진다. 이 때는 동적 계획법을 사용해서 기댓값을 구할 수 있다. dp(i, j) : j번 이후 결과가 i일 확률이라고 하면, n번 이후 결과가 1일 확률이 기댓값이 된다. 이들을 다 더해주면 된다. 

각각의 비트에 대해서 그때 그때 문제를 풀어주면 O(NlgK) 에 문제가 해결되지만, 사실 x와 k로 가능한 경우가 4가지기 때문에 O(N)에 테이블을 다 만들어 놓는게 더 낫다. 시간 복잡도는 O(N)이다. 여담으로 O(lgN)도 가능하다.

3. Castle

문제에 적혀있는 쿼리를 그대로 해석하면 하나 하나의 연산량이 매우 크고 더럽다. 몇가지 생각 정리로 이를 단순화하고 시작하자.

* 초기 Add를 통해 문자열을 다 만들어놓고 시작한다. 

* 집합에 문자열을 넣는다고 생각하지 않고 배열에 prefix를 체크한다고 생각한다. 

* 집합에서 suffix를 찾는 대신, 체크된 prefix 중 자신의 suffix인 것의 개수를 센다. 

이렇게 되면 문자열이 정적이기 때문에 전처리가 가능하고, 쿼리가 훨씬 생각하기 단순해진다.

문자열 S의 길이 i prefix를 S[0, i)라 하자. 세번째 쿼리에서, 우리는 S[0, i)의 prefix이면서 suffix인 문자열들을 모두 나열하고, 그것이 체크되어 있는지를 계산해야 한다. 이 나열은 KMP의 failure function을 사용해서 굉장히 효율적으로 (얼마나 효율적이냐면, 문자열 비교를 전혀 수행하지 않고!) 할 수 있다. KMP failure function에 대한 지식이 없다면 다음 **링크**를 참조하라. 

S[0, i)의 가장 큰 prefix면서 suffix는 당연히 S[0, i)이고, 두번째로 큰 prefix면서 suffix는 S[0, fail(i))이다. 세번째로 큰 prefix면서 suffix는 S[0, fail(i))의 두번째로 큰 prefix면서 suffix이기도 하다. 이는 S[0, fail(fail(i)))이다. 이를 반복하면, T의 prefix이면서 suffix인 문자열은, 문자열 S의 길이 {i, fail(i), fail(fail(i)), …, fail^k(i)}의 prefix들이라는 것을 알 수 있다. 고로 failure function을 타고 가면서 이 중 체크된 원소를 세어 주면, 3번째 쿼리를 O(n)에 처리할 수 있다. 

한편, 2번 쿼리와 3번 쿼리가 번갈아서 들어온다고 생각하지 말고, 처음에 2번 쿼리가 잔뜩 들어오고 3번 쿼리가 나중에 들어온다고 생각해 보자. 3번 쿼리로 길이 L의 prefix가 주어지면, L에 대해서는 체크가 안 된 것이 체크가 되었다고 할 가능성이 있지만, 나머지에 대해서는 원래 문제와 동일한 체크 상태를 가진다. 처음에 2번 쿼리가 잔뜩 주어졌다고 생각하고 전처리를 한 후, 나중에 길이 L짜리 쿼리가 들어오면 L만 다시 체크하고 fail(L) 부터는 전처리된 배열을 참고하는 것이다. 

전처리 방법은 간단하다. DP[i] = (i, fail(i), fail^2(i) ... 중 체크된 원소의 개수) 라고 정의하면, DP[i] = (i번의 체크 여부) + DP[fail(i)] 라는 점화식을 유도할 수 있다. 2번 쿼리 정보를 토대로 처음에 전처리를 한후, 이 정보를 사용해서 3번 쿼리를 (L의 체크 여부) + DP[fail(L)] 과 같이 응답해 주면 선형 시간에 모든 문제를 해결할 수 있다. (비밀인데, 사실 그냥 DP[L]을 찍어줘도 맞는다. 데이터가 약하다..)

4. 로봇

원점을 포함하는 rectilinear polygon이 있을 때 두 번 꺾어서 모든 점을 도달할 수 있는지를 찾는 문제이다. 알고리즘 아웃라인은 대충 다음과 같다.

 * 1. 처음에 가로로 움직이고, 이후 세로로 움직여서 도달할 수 있는 모든 영역을 계산

 * 2. 처음에 세로로 움직이고, 이후 가로로 움직여서 도달할 수 있는 모든 영역을 똑같은 루틴으로 계산

 * 3. 둘의 합집합을 구하고 그것이 전체 다각형인지 판별

1/2번 과정은 plane sweeping을 사용해서 해결한다. (2번 과정은 1번 과정과 완전히 동일한 과정임을 주목하라.) 다각형에서 y축에 평행한 선분들은 전부 무시하고, x축에 평행한 선분들만을 이벤트로 관리한다. 선분은 y좌표를 기준으로 std::set에서 관리한다. 

이제 x좌표가 낮은 쪽에서 높은 쪽으로 움직이며 스윕을 할 것이다. 스윕 도중의 x좌표 구간에서 우리가 알아낼 정보는 1) 해당 x축 구간이 다각형 안에 속하는지 2) 속한다면 다각형에서 최대로 볼 수 있는 위치와 최소로 볼 수 있는 위치가 어디인지 이다. 첫번째 정보와 두번째 정보는 set의 lower_bound와 upper_bound를 사용해서 계산할 수 있다. 디테일이 더 있는데, 자세한 설명은 생략한다. 나의 경우에는 "현재 이벤트 중 y좌표가 0 이하인 이벤트의 개수"를 변수로 가지고 다니는 게 도움이 되었다.

1번 정보와 2번 정보를 전부 알아낸 후에, 먼저 1번 정보를 통해서 처음에 x축을 타고 가로로 움직일 수 있는 구간을 찾을 수 있다. 2번 정보는 현재 x좌표 구간에서 위 / 아래로 볼 수 있는 영역을, 직사각형 형태로 표현해 준다. 고로 도달할 수 있는 영역이, 축에 평행한 겹치지 않는 직사각형의 합집합의 형태로 저장되어 있는 것이다. (여기서 x축을 타고 움직일 수 없는 구간에 있는 직사각형은 무시해줘야 한다.) 

이제 직사각형들의 합집합이 전체 다각형을 이루는지 (3번 과정) 판별해야 한다. 이는 축에 평행한 직사각형의 합집합의 넓이가 다각형의 넓이와 일치하는지를 확인하는 것으로 충분하다. 다각형의 넓이는 CCW를 통해서 계산할 수 있고, 축에 평행한 직사각형의 합집합의 넓이는 Plane Sweeping으로 O(NlgN)에 해결할 수 있는 잘 알려진 문제이다 (BOJ 3392 화성 지도 참고.) 이 문제의 풀이는 다음 두 링크로 대체한다. 링크1 링크2 

결과적으로 모든 과정을 O(NlgN)에 수행할 수 있다. O(n) 풀이도 있다고 하는데 솔직히 생각하기 싫다..