BOJ 17308 Getting-Up Syndrome

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

17308번: Getting-Up Syndrome

 

지문이 영어인데다 길지만 정리하자면 0부터 $m$ 사이의  주어진 쿼리의 연산들을 모두 적용했을 때, 나올 수 있는 값으로 가장 큰 값을 찾으리는 뜻입니다. 숫자를 각각의 비트로 나눠서 생각해주면 그리디하게 해결할 수 있습니다.

 

이러한 비트 연산 종류의 문제에서, 각 비트는 다른 비트에 영향을 주지 않으므로 각각의 비트가 1일 때와 0일 때 주어진 연산들을 거치면 어떤 값이 되는지를 구합니다. 그러면 어떤 수 $x$에 대해서 해당 수가 모든 연산을 거쳤을 때 어떻게 변하는지를 $\mathcal{O}(1)$에 구할 수 있습니다. 그러나 이를 0부터 $m$ 사이의 모든 수에 대해 확인한 후 최댓값을 구하면 $\mathcal{O}(m)$의 시간이 필요합니다.

 

이를 그리디한 방법을 통해 최적화 해 줄수 있습니다. 최상위 비트부터 확인하며 해당 비트에 1을 넣을 수 있는지 확인합니다. 해당 비트에 1을 넣었을 때 $m$보다 커진다면 1을 넣을 수 없는 경우, 그렇지 않다면 1을 넣을 수 있는 경우입니다. 1을 넣을 수 있다면 1과 0중에서 값이 더 커지는 쪽을(같다면 0을), 그렇지 않다면 0을 넣어줍니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define int long long

using namespace std;

int T, n, m;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n >> m;

    bitset<32> ones;
    bitset<32> zeros;

    ones.set();
    zeros.reset();

    while (n--) {
      string s;
      int t;
      cin >> s >> t;

      if (s == "OR") {
        ones = bitset<32>((int)ones.to_ullong() | t);
        zeros = bitset<32>((int)zeros.to_ullong() | t);
      }
      if (s == "XOR") {
        ones = bitset<32>((int)ones.to_ullong() ^ t);
        zeros = bitset<32>((int)zeros.to_ullong() ^ t);
      }
      if (s == "AND") {
        ones = bitset<32>((int)ones.to_ullong() & t);
        zeros = bitset<32>((int)zeros.to_ullong() & t);
      }
    }

    int flag = 0;
    bitset<32> ans;
    bitset<32> mm(m);

    for (int i = 31; i >= 0; i--) {
      int bit = ones[i] | zeros[i];
      int mbit = mm[i];

      if (mbit) {
        ans[i] = bit;
        if (zeros[i] == bit) flag++;
      }
      else {
        if (flag) ans[i] = bit;
        else ans[i] = zeros[i];
      }
    }

    cout << (int)ans.to_ullong() << endl;
  }

  return 0;
}