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; }