TCO 2012 Round 2A easy: SwitchesAndLamps
解法
ある整数集合 S について, S の任意の要素 el がすべての実験で同じ switch の入力をするとすると, それらのスイッチはどうやっても区別することは出来ないので, 「すべての実験で同じスイッチの入力をするような整数の集合」をグループ分けします。
グループ分けしたスイッチについて, ランプの付き方が矛盾していないか確認し, 矛盾してたら -1 を返します。
矛盾してない場合は, 要素数が最大のグループを調べるのに一番時間がかかるので, 最大グループについて調べる方法を考えればよいですが, 1 回の実験で残り調べるべきスイッチの数は size = (size+1)/2 となるので, size = 1 になるまでこれを繰り返せば OK です。
bool done[55]; class SwitchesAndLamps { public: int theMin(vector <string> sw, vector <string> lamps) { int n = sw[0].size(), m = sw.size(); memset(done, false, sizeof(done)); int maxSize = 0; for (int i = 0; i < n; i++) { if (done[i]) continue; int ss = 0, sl = 0; for (int j = i; j < n; j++) { bool same = true; for (int k = 0; k < m; k++) { same &= sw[k][i] == sw[k][j]; } if (same) { ss++; done[j] = true; } } for (int j = 0; j < n; j++) { bool same = true; for (int k = 0; k < m; k++) { same &= sw[k][i] == lamps[k][j]; } if (same) sl++; } if (ss != sl) return -1; maxSize = max(maxSize, ss); } int ret = 0; while (maxSize > 1) { ret++; maxSize = (maxSize+1)/2; } return ret; } };