SRM 694 div2 medium DistinguishableSetDiv2

問題

問題概要

n人の人に対して、m個の質問をした。n人の人がそれぞれの問題に対してどのように答えたが与えられている。m個の問題の中から、問題の部分集合を考え、その時の問題に対するn人の解答のみから、n人全員を区別できるか判定する。これをm個の問題に対して、考えられる部分集合2^m個すべて考えた時、n人を区別できる場合は何通りあるかを求める問題。

解法

2ビット全探索で解いた。問題のセットをビットmaskが1の部分として、そのセットの時に、それぞれの人の解答がどのようになるかを、文字列として求め、setに入れる。setのサイズが人数と同じなら、それぞれの人の解答が異なっていたということになり、その時の問題セットはn人の人を区別することができる。これをすべての問題セット(問題の集合)に対して行い、区別できる問題セットの集合数を求めればよい。

ミス

問題文は何をいっているのかすこしわかりにくかったけど、サンプルから推測した。問題自体はいつもより簡単め？

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;


class DistinguishableSetDiv2{
public:
    int count(vector <string> answer){
        int n = answer.size();
        int m = answer[0].size();
        int ans = 0;
        //bit全探索
        for (int mask = 0; mask < (1 << m); ++mask){
            set<string> se;
            for (int i = 0; i < n; ++i){
                string tmp = "";//i番目の人の解答を文字列として入れる
                for (int p = 0; p < m; ++p){
                    if(mask & (1 << p)){
                        tmp += answer[i][p];
                    }
                }
                se.insert(tmp);
            }
            if(se.size() == n){
                ans++;
            }
        }
        return ans;
    }
};