解いた問題のソースコードと解説など。


SRM 569 Div1 Easy TheDevice

問題

長さの同じN個の文字列がある。文字列は0か1で構成されている。ある機械があり、これはN個の文字列のうちの2枚を入力とし、各桁に対してANDかORかXORを行った(桁ごとにAND, OR, XORのどれを行うかは異なる。)結果を出力する機械である。各桁が行う処理を同定するために必要な追加の文字列の数を求めよ。

やりかた

3つの演算を同定するには0,1,1があれば行うことができる。
0,1 -> 0 && 1,1 -> 1 となるとAND
0,1 -> 1 && 1,1 -> 1 となるとOR
0,1 -> 1 && 1,1 -> 0 となるとXOR

よってN個の文字列の桁毎を見たときに、足りない0の数+足りない1の数が分かるので、この数を各桁について求め、その最大値を返せばよい。

以下ソース。

class TheDevice {
public:
  int minimumAdditional(vector <string> plates) {
    int result = 0;
    int N = plates.size();
    int M = plates[0].length();
    for(int i = 0; i < M; i++){
      int c[2] = {0, 0};
      for(int j = 0; j < N; j++) c[plates[j][i] - '0']++;
      result = max(result, max(1 - c[0], 0) + max(2 - c[1], 0));
    }
    return result;
  }
};

なんで本番でできなかったんですかね。

しょげないでよBaby 眠れば治る