AOJ : 1122 - What is the Number in my Mind ?

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1122
謎の nケタの数字がある.
問題では, nケタの予想数とそれに関するヒット数＆ブロー数が, m回入力される.
このとき, 謎の数字を当てる問題. ただし, 当てられない場合とか1通りに決まらないときは, NOと出力.

アルゴリズム

単純なO(10!)の全探索ではとおらないようです.(国内予選本番では大丈夫でしょうが)
というわけで, 少し枝刈して無理やり通しましょう.

ちなみに, 僕の場合は, ヒット数が 0 の場合の入力を利用して枝刈しました.
(運まかせなやり方)

プログラム

int n,m;
int h[100],b[100];
bool bad[10][10]; //各桁で使ってはいけない値
vector<int> t[100],val,ans;

//ヒット数とブロー数が合っているかの判定
bool check(bool *used){
  for(int i=0;i<m;i++){
    int hit=0, blow=0;
    for(int j=0;j<n;j++){
      if(val[j] == t[i][j]){
        hit++;
      }
      else if(used[t[i][j]]){
        blow++;
      }
    }
    if(hit!=h[i] || blow!=b[i]) return false;
  }
  return true;
}

bool solve(int idx,bool *used){
  if(idx == n){
    if(!check(used)) return true;
    if(!ans.empty()) return false; //2つ以上答えがあるとNO
    ans = val;
    return true;
  }

  for(int i=0;i<10;i++){
    if(used[i] || bad[idx][i]) continue;
    used[i] = true;
    val[idx] = i;
    if(!solve(idx+1,used)) return false;
    used[i] = false;
  }

  return true;
}

int main(void){
  while(cin>>n>>m,n||m){
    memset(bad,0,sizeof(bad));
    for(int i=0;i<m;i++){
      string s;
      cin>>s>>h[i]>>b[i];
      t[i].clear();
      for(int j=0;j<n;j++){
        t[i].push_back(s[j]-'0');

        //ヒット数が0なら各桁で使ってはいけない値がわかる
        if(h[i] == 0) bad[j][t[i][j]] = true;
      }
    }

    bool used[10];
    memset(used,0,sizeof(used));
    ans.clear();
    val = vector<int>(n);
    bool flg = solve(0,used);

    if(flg && !ans.empty()){
      for(int i=0;i<n;i++) cout<<ans[i];
      cout<<endl;
    }
    else{
      cout<<"NO\n";
    }
  }

  return 0;
}