AOJ 2590 Unknown Switches - たわし日和

AOJ-ICPCの200問題
めっちゃ悩んだ　つらかった

問題要約

電源スイッチの操作状況 S (オンオフではなく、スイッチの状態を変えたか)と電球が点灯しているかどうか B が与えられる
電源スイッチと電球の対応を出力せよ

電源スイッチとの対応関係が分かる電球の場合、対応する電源スイッチの番号を出力し
電源スイッチとの対応関係が不明な電球の場合、「?」と出力せよ

解法

電源スイッチと電球の対応表を作り、
電源スイッチの状態（オンかオフか）と電球の状態（点灯しているかしていないか）が食い違う場合、電源スイッチと電球が対応していないと記録する

電源スイッチと電球の対応が１対１に定まるとき該当の電源スイッチの番号を出力し、
定まらない場合は「?」を出力する

さてこんなわけのわからないたわし語を用いたたわしの説明よりスライドを見た方が早い
というわけでこちらが公式の解説スライドです
http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2014%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=B.pdf

import java.util.*;
public class Main { 
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    while(true) {
      int n = stdIn.nextInt();
      int m = stdIn.nextInt();
      int q = stdIn.nextInt();
      if(n == 0 && m == 0 && q == 0) break;
      String[] S = new String[q];
      String[] B = new String[q];
      for(int i = 0; i < q; i++) {
        S[i] = stdIn.next();
        B[i] = stdIn.next();
      }
      boolean[][] SX = new boolean[q][n];
      boolean[][] BX = new boolean[q][m];
      for(int i = 0; i < q; i++) {
        for(int j = 0; j < n; j++) {
          SX[i][j] = (S[i].charAt(j) == '1')?true:false;
        }
        for(int j = 0; j < m; j++) {
          BX[i][j] = (B[i].charAt(j) == '1')?true:false;
        }
        if(i != 0) {
          for(int j = 0; j < n; j++) {
            SX[i][j] = (S[i].charAt(j) == '1')?!SX[i-1][j]:SX[i-1][j];
          }
          for(int j = 0; j < m; j++) {
            BX[i][j] = (B[i].charAt(j) == '1')?true:false;
          }
        }
      }
      boolean[][] list = new boolean[n][m];
      for(int i = 0; i < q; i++) {
        for (int j = 0; j < n; j++) {
          if (SX[i][j]) {
            for (int k = 0; k < m; k++) {
              if (!BX[i][k]) {
                list[j][k] = true;
              }
            }
          }
          if (!SX[i][j]) {
            for (int k = 0; k < m; k++) {
              if (BX[i][k]) {
                list[j][k] = true;
              }
            }
          }
        }
        
      }
      if(n == 1) {
        for(int i = 0; i < m; i++) {
          System.out.print(0);
        }
        System.out.println();
        continue;
      }
      int[] ans = new int[m];
      for(int i = 0; i < m; i++) {
        ans[i] = -1;
        int count = 0;
        int id = 0;
        for(int j = 0; j < n; j++) {
          if(!list[j][i]) {
            id = j;
            count++;
          }
        }
        if(count == 1) {
          ans[i] = id+1;
        }
      }
      for(int i = 0; i < ans.length; i++) {
        if(ans[i] == -1) {
          System.out.print("?");
        }
        else if(ans[i] <= 10) {
          char a = '0';
          a += ans[i]-1;
          System.out.print(a);
        }
        else {
          char a = 'A';
          a += (ans[i] - 11);
          System.out.print(a);
        }
      }
      System.out.println();
    }
  }
}