백준 20106: Cave

https://www.acmicpc.net/problem/20106

20106번: Cave

번역본은 https://oj.uz/problem/view/IOI13_cave를 참고하시면 됩니다.

 

풀이

시행이 최대 70,000번이며, $N$이 최대 5,000이기 때문에 $N\lg N$번의 tryCombination함수 호출로 문제를 해결해야 합니다. 즉, 하나의 스위치당 $\lg N$번의 시행으로 정답 위치와 연결된 문을 찾으면 됩니다.

 

당연하게도 이분탐색으로 접근하면 됩니다. $ans[i]$를 스위치 $i$의 정답 위치, $match[i]$를 스위치 $i$에 연결된 문이라고 선언합니다. $0$번부터 $N-1$번까지의 문에 대해 순서대로 $match[i]$값이 그 문의 값이 되는 $i$를 이분탐색으로 찾아보도록 하겠습니다.

현재 $i$번 문에 연결된 스위치를 찾는 상태라면, $0$부터 $i-1$번 문까지는 연결된 스위치와 그 스위치의 정답 위치를 알고 있을 것입니다. 그 $i$개의 스위치들을 모두 정답 위치로 고정해놓고, 나머지 스위치는 모두 상태 $0$으로 돌려놓고 tryCombination()함수를 호출하여 초기 $i$번 문의 상태를 저장합니다(함수의 리턴값이 $i$면 닫힌 상태, $i$가 아니면 열린 상태).

$l$번부터 $r$번 사이에 저희가 찾는 스위치가 있다고 합니다(초기에는 $l=0,\ r=N-1$이 됩니다). $mid=(l+r)/2$라 하고, 스위치 $l$번부터 $mid$번까지를 앞서 고정한 스위치들을 빼고 모두 반전시킵니다. 그리고 tryCombination함수를 호출하여 문 $i$가 상태가 이전과 바뀌었는지 확인해봅니다. 만일 바뀌었다면, 문에 연결된 스위치는 반전시킨 구간인 $l$부터 $mid$ 중에 있는 것이고, 바뀌지 않았다면 $mid+1$부터 $r$ 중에 있는 것입니다. 이를 $\lg N$번 반복하여 문 $i$와 연결된 스위치를 찾을 수 있습니다.

그 스위치의 정답 위치는 이분탐색 종료 직전에 확인한 문 $i$의 상태와 스위치의 상태로 구할 수 있습니다.

 

코드

 

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int ans[5000], match[5000];
void exploreCave(int n) {
    memset(match, -1, sizeof(match));
    for(int i=0; i<n; i++) {
        int s[5000]={0};
        for(int j=0; j<n; j++) if(match[j]!=-1) s[j]=ans[j];
        bool b=(tryCombination(s)==i);
        int l=0, r=n-1;
        while(l<r) {
            int mid=(l+r)/2;
            for(int j=l; j<=mid; j++) if(match[j]==-1) s[j]=!s[j];
            bool t=(tryCombination(s)==i);
            if(t==b) l=mid+1;
            else b=t, r=mid;
        }
        match[l]=i;
        ans[l]=s[l]^b;
    }
    answer(ans, match);
}