Codeforces Round #44 (Div 2) D. Safe

問題概要

0,1の列からなるn文字のパスワードがある。
これに対してm個のn文字の0,1の列からなるパスワード誤入力の列および、
その列におけるパスワードと一致している文字数が与えられる。
（一致の個数だけで、どの位置が一致しているかは与えられない）

このとき、パスワードの文字列としてありうるものの個数を求めよ。
一致している文字数はそれぞれ5以下、n≤35,m≤10である。

解法

一つの誤入力文字列に着目する。
一致している文字は5以下なので、正しいパスワードの候補は35C5通り(=数十万）以下に絞れる。
よって、そのようなそのような候補を全て試してみることができる。

位置iの正誤をビットで表そうとするとlong longを使わないといけないことに注意する。

ソースコード

int n,m,cr[10],ans;
string in[10];

bool ck(ll b){
  rep(i,m){
    int c=0;
    rep(j,n)if(in[i][j]-'0'==!!(b&1LL<<j))c++;
    if(c!=cr[i])return 0;
  }
  return 1;
}
void rec(int c,int u,ll b){
  if(u>cr[0])return;
  if(c==n){
    if(u<cr[0])return;
    rep(i,n)b^=1LL-(in[0][i]-'0')<<i; 
    if(ck(b))ans++;
    return;
  }
  rec(c+1,u+1,b^1LL<<c);
  rec(c+1,u,b);
}

void run()
{
  cin>>n>>m;
  pair<int,string> p[m];
  rep(i,m)cin>>p[i].second>>p[i].first;
  sort(p,p+m);
  rep(i,m)cr[i]=p[i].first,in[i]=p[i].second;

  ans=0;
  rec(0,0,0);
  cout<<ans<<endl;
}