Codeforces Round #443 (Div. 1) A. Short Program

Codeforces Round #443 (Div. 1) A. Short Program

나는 왜 이런문제를 못푸는지 모르겠다.

하... 이 코포셋이 나온지는 6주나 지났는데,

요즘 한 두달간 뻘짓만 하다가 다시 정신차리고 문제를 풀기 시작했다.

일단 이 문제는 xor, and, or 연산을 하는데,

문제에서 주어지는 최대 50만개의 연산을 진행한 뒤

이 값과 똑같은 값을 출력하는 5개 이하의 XOR, AND, OR 연산 조합을 출력해야한다.

이 문제의 핵심은 다음과 같다.

1. 0과 AND 연산을 한다면 반드시 0이 출력되어야 한다.

2. 1과 OR 연산을 한다면 반드시 1이 출력되어야 한다.

3. 임의의 x번째 비트가 AND와 OR연산의 영향을 받지 않을 때에만 XOR 연산의 영향을 받는다.

이 3가지만 고려하면 문제를 풀 수 있다.

나는 해당 방법을 한참 고민했으나 풀 수 없었고,

코포 Editorial과 dotorya님 코드를 참고했다.

AC받은 코드는 다음과 같다.

#include <cstdio>
using namespace std;
int v[10];
int main() {
    int n; scanf("%d", &n);
    for(int i=0; i<10; i++) v[i]=2;
    while(n--) {
        char s[2]; int t;
        scanf("%s %d", s, &t);
        if(s[0]=='|') {
            for(int i=0; i<10; i++) {
                if((t>>i)&1) v[i]=1;
            }
        } else if(s[0]=='&') {
            for(int i=0; i<10; i++) {
                if(!((t>>i)&1)) v[i]=0;
            }
        } else {
            for(int i=0; i<10; i++) {
                if((t>>i)&1) v[i]^=1;
            }
        }
    }
 
    int AND=0,OR=0,XOR=0;
    for(int i=0; i<10; i++) {
        if(v[i]==0) AND |= (1<<i);
        else if(v[i]==1) OR |= (1<<i);
        else if(v[i]==3) XOR ^= (1<<i);
    }
 
    printf("3\n");
    printf("& %d\n", AND^1023);
    printf("| %d\n", OR);
    printf("^ %d\n", XOR);
    return 0;
}