Codeforces Round #402 (Div. 2) E. Bitwise Formula
# 問題
http://codeforces.com/contest/779/problem/E
Mビットからなる変数がN個与えられます。各変数は、代入か、異なる2つの変数の AND OR XOR のいずれかの結果です。すべての変数の合計値が最小になるような変数 '?' と最大になるような変数 '?' を求めてください。
# 解法
各bitについて0のときと1のときを計算し、大きい方を採用すると、結果として全体を最大にするビットになる。
# コード
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; import java.util.TreeMap; public class E { enum OP { XOR, OR, AND } class Operation { final int key1; final int key2; final OP op; Operation(int key1, int key2, OP op) { this.key1 = key1; this.key2 = key2; this.op = op; } } Operation[] operations; String[] variables; int[] tmp; int dfs(int key, int value, int pos) { if (tmp[key] >= 0) { return tmp[key]; } if (variables[key] != null) { return variables[key].charAt(pos) - '0'; } if (operations[key] == null) { throw new IllegalArgumentException(); } Operation operation = operations[key]; int key1 = operation.key1; int v1 = key1 >= 0 ? dfs(key1, value, pos) : value; int key2 = operation.key2; int v2 = key2 >= 0 ? dfs(key2, value, pos) : value; switch (operation.op) { case AND: tmp[key] = v1 & v2; break; case OR: tmp[key] = v1 | v2; break; case XOR: tmp[key] = v1 ^ v2; break; } return tmp[key]; } private void solve(Scanner in, PrintWriter out) { String[] nm = in.nextLine().split(" "); int N = Integer.parseInt(nm[0]); int M = Integer.parseInt(nm[1]); TreeMap<String, Integer> shrink = new TreeMap<>(); shrink.put("?", -1); operations = new Operation[N]; variables = new String[N]; tmp = new int[N]; String[][] formulas = new String[N][]; for (int i = 0; i < N; i++) { String[] formula = in.nextLine().split(" "); String key = formula[0]; shrink.put(key, i); formulas[i] = formula; } for (String[] formula : formulas) { String key = formula[0]; int i = shrink.get(key); if (formula.length == 3) { variables[i] = formula[2]; } else { int key1 = shrink.get(formula[2]); int key2 = shrink.get(formula[4]); OP op = OP.valueOf(formula[3]); operations[i] = new Operation(key1, key2, op); } } char[] max = new char[M]; for (int pos = 0; pos < M; pos++) { Arrays.fill(tmp, -1); int result0 = 0; for (int i = 0; i < N; i++) { result0 += dfs(i, 0, pos); } Arrays.fill(tmp, -1); int result1 = 0; for (int i = 0; i < N; i++) { result1 += dfs(i, 1, pos); } if (result0 >= result1) { max[pos] = '0'; } else { max[pos] = '1'; } } char[] min = new char[M]; for (int pos = 0; pos < M; pos++) { Arrays.fill(tmp, -1); int result0 = 0; for (int i = 0; i < N; i++) { result0 += dfs(i, 0, pos); } Arrays.fill(tmp, -1); int result1 = 0; for (int i = 0; i < N; i++) { result1 += dfs(i, 1, pos); } if (result0 <= result1) { min[pos] = '0'; } else { min[pos] = '1'; } } out.println(new String(min)); out.println(new String(max)); } public static void main(String[] args) { PrintWriter out = new PrintWriter(System.out); new E().solve(new Scanner(System.in), out); out.close(); } }