mayoko’s diary

プロコンとかいろいろ。

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