Problem Solving Diary #4

BOJ 20641. Sleeping Cows

문제에서 요구하는 조건은 크게 두 가지입니다.

• 모든 소가 하나의 헛간에 들어갈 수 있도록 선택할 것
• 선택하지 않은 소들은 모두 선택하지 않은 헛간보다 크기가 클 것

2번 조건을 다른 말로 표현하면, "선택하지 않은 가장 작은 소"가 "선택하지 않은 가장 큰 헛간"보다 크면 됩니다. 따라서 선택하지 않은 가장 작은 소를 고정하고, 2차원 DP를 돌리면 $O(N^3)$ 풀이가 나옵니다. DP에 대해 간단히 설명하면 우선 헛간과 소를 모두 한 배열에 넣고 크기 순으로 정렬한 뒤, 왼쪽부터 차례로 보면서 그 인덱스를 i, (지금까지 선택한 소의 수 - 지금까지 선택한 헛간의 수)를 j로 정의하면 됩니다.

 

이제 $N$을 하나 떼어 봅시다. 선택하지 않은 가장 작은 소의 크기를 $x$라고 합시다. $x$보다 큰 소는 모두 선택해야 하고, $x$ 이하의 헛간 역시 모두 선택해야 합니다. 여기서 $x$의 값이 $y$일 때와 $y+1$일 때 무슨 차이가 있을까요? 크기가 $y$ 이상 $y+1$ 이하인 헛간이나 소를 점검할 때 작은 차이가 생길 것입니다. 이런 관점에서, $x$를 굳이 고정할 필요가 없습니다. 우리가 중요한 것은 현재 보고 있는 소나 헛간의 크기가 $x$ 이상인지의 여부만이 중요할 뿐입니다.

 

따라서 아래와 같이 DP를 재정의할 수 있습니다.

 

$DP[i][j][k]$: 지금 $i$번째 (헛간 또는 소)를 보고 있고, 아직 소가 들어가지 않은 선택된 헛간이 $j$개이다. 최종 결과에서 선택되지 않은 가장 크기가 작은 소의 크기를 "분기점"이라고 하자. 만약 $k=0$이면 아직 분기점에 도달하지 못했고, $k=1$이면 분기점에 이미 도달한 후이다.

 

이렇게 DP 식을 정의하면 제곱에 문제가 풀립니다. 다소 풀이 설명이 복잡하기 때문에, 이해를 도울 코드를 첨부합니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

int n;
int a[3002], b[3002];
vector<pair<int, bool> > vec;
ll DP[6002][3002][2];

int main(){
    scanf("%d", &n);
    vec.push_back(make_pair(0, 0));
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), vec.push_back(make_pair(a[i], 0));
    for(int j=1; j<=n; j++) scanf("%d", &b[j]), vec.push_back(make_pair(b[j], 1));
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    sort(vec.begin(), vec.end());

    DP[0][0][0] = 1;
    DP[0][0][1] = 1;
    for(int i=1; i<=n*2; i++){
        for(int j=0; j<=n; j++){
            for(int k=0; k<2; k++){
                if(vec[i].second == 0){ /// 소 -> k=0이면 무조건 사용, k=1이면 선택 가능
                    DP[i][j+1][k] = (DP[i][j+1][k] + DP[i-1][j][k]) % MOD;
                    if(k) DP[i][j][k] = (DP[i][j][k] + DP[i-1][j][k]) % MOD;
                }
                else{ /// 헛간 -> k=0이면 선택 가능, k=1이면 무조건 사용
                    if(j) DP[i][j-1][k] = (DP[i][j-1][k] + DP[i-1][j][k] * j) % MOD;
                    if(!k){
                        DP[i][j][k] = (DP[i][j][k] + DP[i-1][j][k]) % MOD;
                        DP[i][j][1] = (DP[i][j][1] + DP[i-1][j][k]) % MOD;
                    }
                }
            }
        }

//        printf("i = %d: ", i);
//        for(int j=0; j<=n; j++){
//            printf("(%lld, %lld) ", DP[i][j][0], DP[i][j][1]);
//        }
//        puts("");
    }

    printf("%lld", DP[n+n][0][1]);
}

 

BOJ 5493. Empodia

수열의 각 원소를 $(i, a_i)$ 위치에 플로팅합시다. 이제 왼쪽부터 차례대로 원소를 보면서, 현재 $i$번 원소를 보고 있다고 할 때 $x < i$인 점들만 생각합시다. 어떤 점을 봤을 때, 그 점 오른쪽에 자기보다 높은 점이 없다면 그 점은 upper monotone chain의 점이 됩니다. 반대로, 그 점 오른쪽에 자기보다 낮은 점이 없다면 그 점은 lower monotone chain의 점이 됩니다.

 

모든 empodia는 양 끝점을 제외하면 서로 겹치지 않으므로, 왼쪽부터 empodia를 하나씩 찾는 전략을 사용해 봅시다. 현재 보고 있는 점인 $i$번 점을 맨 오른쪽 끝점으로 하는 empodia가 존재한다면, 해당 empodia $[l, i]$는 아래 조건을 만족합니다.

• $a_l - l = a_i - i$
• $l \le j \le i$인 모든 $j$에 대해, $a_l \le a_j \le a_i$

따라서 자명하게도 $l$은 lower monotone chain의 원소 중 하나가 됩니다. 이 $l$은 lower monotone chain의 원소들 중 $a_l - l = a_i - i$인 가장 큰 원소가 될 것입니다. 두 번째 조건을 만족하는지만 판별해 주면 되는데, 세그를 짜거나 앞서 언급한 upper monotone chain을 이용한 이분 탐색으로 확인해 줄 수 있습니다.

 

BOJ 17679. Minerals (~90점)

서브태스크 2 (25점)

왼쪽 $N$개의 시료와 오른쪽 $N$개의 시료 사이의 매칭을 찾아 주면 됩니다. 쿼리 제한 $Q \sim 4N \log N$임을 이용합시다. 쿼리 복잡도에 로그가 들어가기 때문에 이분 탐색을 생각해 볼 수 있습니다. 하지만 이분 탐색을 단순히 하기에는 일일히 장치에 삽입하는 것이 어렵기 때문에 병렬로 전체 이분 탐색을 돌려야 합니다. 병렬 이분 탐색의 구조를 잡으면 결국 세그먼트 트리와 같은 구조가 될 것이고, 세그먼트 트리를 탐색하듯이 매칭해 주면 어렵지 않게 $3N \log N$번의 연산으로 답을 찾을 수 있습니다.

 

서브태스크 1, 3 (40점)

시료를 두 그룹으로 분할할 수만 있다면 위의 방법을 그대로 쓰면 됩니다. 시료를 앞의 것부터 차례로 추가해 나가면서 가짓수가 늘어나는 것과 늘어나지 않는 것으로 분할하면 $N$가지 시료로 이루어진 그룹 두 개가 생깁니다. 이 두 그룹에 서브태스크 2의 풀이를 적용하면 됩니다.

 

서브태스크 4, 5, 6 (80점)

세그먼트 트리에서 연산하는 부분을 더 최적화해 봅시다. 왼쪽 반절만 켜져 있도록 만드는 과정을 계속 해 주면 $\frac{3}{2} N \log N + N$번의 연산에 문제가 풀립니다. 이걸 실제로 짜면 80점이 나옵니다.

 

서브태스크 7, 8 (90점)

편의상 A그룹, B그룹으로 미네랄들을 나눠 부르겠습니다. A그룹의 $[l, r]$ 사이에 어떤 B그룹의 광물 $x$가 포함된다는 사실을 알고 있다고 해 봅시다. 이러한 $x$의 목록을 이미 앞에서 구해 놓은 상태입니다. 여기서 광물 목록의 마지막 광물은 굳이 쿼리를 사용하지 않아도 간단한 개수 비교로 $[l, m]$에 속하는지, $[m+1, r]$에 속하는지 알 수 있습니다. 이렇게 하면 $N$번의 쿼리를 제거할 수 있고, $\frac{3}{2} N \log N$번의 쿼리에 문제를 풀 수 있습니다. 90점이 나옵니다.

 

BOJ 16531. KryptoLocker Ate my Homework

모든 원소가 양수라고 가정해 봅시다. 이때는 0 다음으로 큰 값이 수열의 원소 $x$가 됩니다. 이제 길이 $2^N$ 배열의 원소의 값 $v$를 작은 것부터 보면서, $v+x$를 배열에서 삭제해 주면 $x$가 없는 배열에 대한 새로운 $2^{N-1}$ 길이의 배열을 얻을 수 있습니다. 이 과정을 반복하면 됩니다.

 

음수 원소가 있다면, 가장 작은 값은 해당 음수 원소들의 합입니다. 그렇다면 반대로 해당 음수 원소들이 모두 절댓값으로 바뀐다면 어떻게 될까요? 가장 작은 값은 0이 되며, 모든 값이 해당 절댓값 합만큼 늘어날 것입니다. 이 상태로 모든 수가 양수일 때의 문제를 푼 뒤, 음수인 값들의 합을 만들 수 있는 모든 조합을 테스트해 보면 됩니다.

 

BOJ 14164. 삼각형 영역

삼각형의 세 꼭짓점 번호를 $i$, $j$, $k$라고 할 때, $j-k$ 간선을 고정하고 문제를 풀어 봅시다. 우선 $i<j$인 모든 $i$번 꼭짓점은 $jk$ 직선을 기준으로 양쪽 두 반평면 중 하나에 있는데, 편의상 같은 반평면에 있는 꼭짓점들만 고려합시다. (이렇게 하는 이유는 삼각형 $ijk$ 안에 점 $l$이 있으려면, $i$와 $l$은 $jk$를 기준으로 같은 반평면에 있어야 하기 때문입니다.) 어느 쪽 반평면에 있는지는 $ccw(i, j, k)$의 부호로 판별할 수 있습니다.

 

어느 세 점도 한 직선 위에 있지 않으므로, $\angle ijk$ 를 기준으로 점 $i$를 모두 정렬할 수 있습니다. 각도를 직접 구하면 실수 오차 문제가 생길 수 있으므로, $ccw(i, j, i')$의 부호로 비교가 가능합니다. 마찬가지로 $\angle ikj$ 기준으로도 정렬해 둡니다.

 

점 $i'$가 $\triangle ijk$ 안에 포함될 조건은 다음과 같습니다.

• $\angle ijk > \angle i'jk$ 이고,
• $\angle ikj > \angle i'kj$

이제 $i$까지 고정하고 위 두 조건을 모두 만족하는 $i'$의 개수를 세면 되는데, 이것은 간단한 형태의 2d query를 해결하는 문제가 되고, 펜윅 트리와 스위핑을 이용한 $O(N \log N)$ 해법이 잘 알려져 있습니다. 따라서 전체 시간 복잡도는 $O(N^3 \log N)$이 됩니다.

 

위 풀이를 그대로 짜면 $j < i'$인 경우를 처리하지 못하는데, 이 경우를 처리하는 것은 그렇게 어렵지 않습니다.

 

BOJ 16476. decrypt

일단 $R$의 주기에 대한 관찰이 필요합니다. $R[0]=A$, $R[1]=B$, $R[2]=C$로 놓고 $R$의 첫 몇 항을 계산해 보면 $R$이 7의 주기로 반복됨을 알 수 있습니다. 편의상 $A=1$, $B=2$, $C=4$라고 가정합시다. 이때 $R$은 $1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 6 \rightarrow 7 \rightarrow 5$가 반복되는 형태입니다.

 

복잡하게 생각하지 말고 단순하게 0부터 255 사이의 값을 랜덤하게 넣다가, 같은 출력 값이 두 번째 나오는 시점에서 중단해 보기로 합시다. 이를 통해 우리는 $R[i] \oplus I_1 = R[j] \oplus I_2$ (단, $0 \le i < j \le 6$)임을 알 수 있고, 식을 정리하면 $R[i] \oplus R[j] = I_1 \oplus I_2 = v$와 같은 형태의 정보를 알 수 있습니다. 이를 통해 $R$ 배열의 값 중 하나를 $v$로 확정지을 수 있게 됩니다.

 

이론적으로 $R[i]$값을 3~4개만 알면 나머지 값은 모두 추론할 수 있습니다. 따라서 $R[i]$ 값을 몇 개라도 찾는 것을 목표로 해 봅시다. $R[i]$ 값이 만약 전체 $R$배열을 알 수 있도록 충분히 찾아졌다면, 간단한 그래프 탐색(또는 어떤 방법을 사용하더라도)을 통해 나머지 $R$값을 찾아낼 수 있습니다. 이제 $R$을 모두 찾았으니, $M$을 모두 찾는 건 그렇게 어렵지 않습니다.

 

문제는 $R$을 얼마나 빨리 찾을 수 있냐는 건데, 표본이 크더라도 겹치는 두 개의 값을 찾는 데는 그렇게 오래 걸리지 않는다(생일 문제)는 사실이 잘 알려져 있습니다. 그래서 믿음을 가지고 짜면 맞습니다.