ferinの競プロ帳

競プロについてのメモ

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

問題ページ
Problem - 878A - Codeforces

概要

n個(n <= 10^5)のbit操作が書かれたプログラムが与えられる。0から1023までの数がプログラムに入力される。このとき、5個以下のbit操作で同じ操作となるプログラムを出力しろ。

解法

bit操作と言われたので2進数で考える。
まず、sampleを試してみる。-が入力された数そのままの桁、~が入力された数から反転した桁を表す。
sample1

    ----------
| 3 --------11
^ 2 --------01
| 1 --------01

sample2

    ----------
& 1 000000000-
& 3 000000000-
& 5 000000000-

sample3

    ----------
^ 1 ---------~
^ 2 --------~~
^ 3 ----------

こんな感じで試してみると操作1回についてO(logX)で状態を遷移できるのでO(NlogX)で最後の状態が求まることがわかる。
最後の状態にするためには少なくともANDとORとXORを1回ずつ使えば実現可能である。最後の状態が-と~のところを残すようにANDを取り、1のところにORを取り、~のところにXORを取ることで3回のbit操作で実現可能である。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

int dp[20];
signed main(void)
{
  int n;
  cin >> n;
  memset(dp, -1, sizeof(dp));
  REP(i, n) {
    char c;
    int x;
    cin >> c >> x;
    if(c == '&') {
      REP(i, 10) {
        if(!(x & (1<<i))) {
          dp[i] = 0;
        }
      }
    } else if(c == '|') {
      REP(i, 10) {
        if(x & (1<<i)) {
          dp[i] = 1;
        }
      }
    } else {
      REP(i, 10) {
        if(x & (1<<i)) {
          if(dp[i] == -1) dp[i] = 2;
          else if(dp[i] == 2) dp[i] = -1;
          else if(dp[i] == 0) dp[i] = 1;
          else if(dp[i] == 1) dp[i] = 0;
        }
      }
    }
  }


  int a = 0, b = 0, c = 0;
  REP(i, 10) {
    if(dp[i] == -1) a |= 1<<i;
    else if(dp[i] == 1) b |= 1<<i;
    else if(dp[i] == 2) a |= 1<<i, c |= 1<<i;
  }

  cout << 3 << endl;
  cout << "& " << a << endl;
  cout << "| " << b << endl;
  cout << "^ " << c << endl;

  return 0;
}