Codeforces Round #438 (Div.1 + Div.2) C. Qualification Rounds

C. Qualification Rounds

http://codeforces.com/contest/868/problem/C

자꾸 형식에 맞춰서 쓰다보니 PS관련 블로그 쓰는게 귀찮아서 더 안쓰는 거 같다.

그래서 그냥 내 맘대로 끄적이려구 한다...

이 문제는 첫 번째 줄에 n, k가 주어지는데,

n은 문제 수고 k는 팀 수라고 한다.

그 다음 n개의 줄에는 각 문제에 대해 풀 수 있는 팀과 풀 수 없는 팀이 표기되는데,

1이면 풀 수 있고 0이면 풀 수 없다.

이런 n개의 문제 셋에서 아무거나 몇개 골라서

어떤 팀도 전체 문제 중에 반 넘게 풀 수 있는 경우가 생기면 NOT interesting하다고 한다.

그래서 interesting하게 문제 셋을 구성 할 수 있으면 YES를 출력하고 아니면 NO를 출력하는 문제다.

아래와 같은 입력을 예로 들어보자.

input

5 3
1 0 1
1 1 0
1 0 0
1 0 0
1 0 0

output

NO

위 예제를 보면 n=5, k=3이다.

즉, 문제가 5개가 있고 팀이 3팀이 있다는 얘기다.

2번째 줄에 1 0 1이 의미하는 것은 첫번째 문제에 대해서 첫번째 팀은 풀 수 있고 2번째 팀은 풀 수 없고 3번째 팀은 풀 수 있다는 것을 의미한다.

그런데 첫번째 팀이 모든 문제를 풀 수 있으므로 5개의 문제들 중에서 어떤걸 선택하더라도 답은 NO가 되어야 한다.

자... 그럼 어떻게 풀까?

이 문제는 답이 되는 문제 셋이 '다른 두 덩어리의 문제셋'으로 부터 왔음을 이해하면 해결 할 수 있다.

그럼 다른 두 덩어리의 문제셋은 서로 겹치는 비트가 없다는 얘기가 된다.

예를들어 한 덩어리의 문제 셋을 11010010으로 표현한다면, 다른 덩어리의 문제셋은 적어도 1,2,4,7번째 비트가 켜져있으면 안된다는 뜻이다.

그러므로 비트가 겹치지 않는 숫자들만 고려하면 2개의 문제만 선택하는 경우에는 해결이 가능하다.

그런데, 하나의 문제셋은 다른 두 덩어리의 문제셋으로 부터 왔으므로 이를 다시 생각해보면 다른 두 덩어리의 문제셋 또한 각각 다른 두 덩어리의 문제셋으로부터 파생되었음을 알 수 있다.

결론은 2개만 확인해보면 된다는 것이다.

주의할 점은 그 자체로 가능한 0 0 0 (0으로만 구성된 문제 == 모든 팀이 풀 수 없는 문제)만 예외처리 해주면 된다.

#include <iostream>
using namespace std;
bool chk[16];
int main() {
    int n, k; scanf("%d%d",&n,&k);
    for(int i=0; i<n; i++) {
        int s=0,x;
        for(int j=0; j<k; j++) {
            scanf("%d", &x);
            s=s*2+x;
        }
        if(s==0) return 0&puts("YES");
        chk[s]=true;
    }
    for(int i=0; i<(1<<k); i++) {
        for(int j=0; j<(1<<k); j++) {
            if(i&j) continue;
            if(chk[i] && chk[j]) return 0&puts("YES");
        }
    }
    puts("NO");
    return 0;
}