読者です 読者をやめる 読者になる 読者になる

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