TopCoder SRM 569 Div2 Medium TheDeviceDiv2, Div1 Easy TheDevice

さてDiv2 MediumとDiv1 Easy。
これらは若干内容が異なるがほぼ同じなのでまとめて紹介。
http://community.topcoder.com/stat?c=problem_statement&pm=12388
http://community.topcoder.com/stat?c=problem_statement&pm=12399

問題

ある計算機がある。この計算機に２つの２進数を入れると各ビットはXOR, OR, ANDのいずれかの結果を返す。
最大50個の同じ桁数の２進数が与えられたとき：

• Div2 Medium : これらの値を使って各桁がXOR/OR/ANDどの計算手法か十分判断できるか否かを返す
• Div1 Easy : これらの値を使って各桁がXOR/OR/ANDどの計算手法か十分判断できない場合、追加する必要のある最少の２進数の数を返す

解法

各ビットの計算方式がXORかORかANDかを判断するには、各桁で0と1を処理した結果と、1と1を処理した結果が無ければならない。
この両者の結果で、下記の通り各ビットの計算方式が判断できる。

• AND : 0 AND 1=0, 1 AND 1=1
• OR : 0 OR 1=1, 1 OR 1=1
• XOR : 0 XOR 1=1, 1 XOR 1=0

よって、各２進数において、0が１個以上、1が２個以上あればよい。

• Div2 Mediumはこの数に満たなければ判断できないと返せばよい。
• Div1 Easyは、各桁この数に満たない場合の差分の最大値を返せばよい。

まずDiv2 Mediumは下記の通り。

class TheDeviceDiv2 {
	int mask[2][51];
	public:
	string identify(vector <string> P) {
		int i,j,x;
		ZERO(mask);
		
		FOR(i,P.size()) {
			FOR(x,P[i].size()) {
				mask[P[i][x]-'0'][x]++;
			}
		}
		
		FOR(x,P[0].size()) if(mask[0][x]<1 || mask[1][x]<2) return "NO";
		return "YES";
	}
};

続いてDiv1 Easy。

class TheDevice {
	int mask[2][51];
	public:
	int minimumAdditional(vector <string> P) {
		int i,j,x,ma=0;
		;
		ZERO(mask);
		FOR(i,P.size()) {
			FOR(x,P[i].size()) {
				mask[P[i][x]-'0'][x]++;
			}
		}
		
		FOR(x,P[0].size()) ma = max(ma,max(0,1-mask[0][x])+max(0,2-mask[1][x]));
		return ma;
	}

};

まとめ

Div2 Mediumの際0も２個必要だと考えて凡ミスした。
Div1 Easyは１発正解だったが、Div2 Mediumのミスが無ければ本番ではミスっていただろう。
今回出なくて良かった…。