AOJ1161 Verbal Arithmetic

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1161

覆面算を解け。ただし、以下の条件を満たす。

• 
• 異なる文字で同じ値が重複してはならない
• 複数桁ある数の時、先頭の数字は0であってはならない
• 

解説
以下のサイトを見させて頂きました。
http://d.hatena.ne.jp/kkishi/20090707/1246930309

このサイトに書いてある以上のことは書けないので、特別解説はしません。
AOJの実行速度が昔に比べて速くなっているので、一つ目の係数のみをみる単純な解法でも十分な速度で通ります。

bool forbid_0[10];
int coef[10];
int ASize;
bool used[10];
int sum;

int dfs(int idx) {
  int ret = 0;
  if(idx == ASize) return sum == 0;

  rep(digit, 10) {
    if(digit == 0 && forbid_0[idx]) continue;
    if(used[digit]) continue;
    used[digit] = 1, sum += coef[idx] * digit;
    ret += dfs(idx + 1);
    used[digit] = 0, sum -= coef[idx] * digit;
  }
  return ret;
}

int main() {
  int N;
  while(cin >> N && N) {
    vector<string> v(N);

    string alphs;
    rep(i, N) {
      cin >> v[i];
      alphs += v[i];
    }

    // ACM, IBM, ICPC => {A,B,C,I,M,P} 文字列alphsとして順に並べる
    sort(all(alphs)); alphs.erase(unique(all(alphs)), alphs.end());

    /*
      各文字の係数を先に計算する
      ACM + IBM = ICPC より、
      100*A+10*C+M + 100*I+10*B+M = 1000*I+101*C+10*P
      100*A +10*B -91*C -900*I +2*M -10*P = 0
      これを満たすようなA, B, C, I, M, Pの値を求める
      */

    // alphs上の位置を特定する
    vector<vector<int>> pos(N);
    rep(i, N) rep(j, v[i].size()) pos[i].push_back(alphs.find(v[i][j]));

    rep(i, 10) coef[i] = 0;

    // 左辺を足す
    rep(i, N-1) rep(j, pos[i].size()) coef[pos[i][j]] += pow(10, (int)pos[i].size()-1-j);

    // 右辺を引く
    rep(i, pos.back().size()) coef[pos.back()[i]] -= pow(10, (int)pos.back().size()-1-i);

    // 0を取れないアルファベットを特定する
    rep(i, 10) forbid_0[i] = 0;
    rep(i, N) if(pos[i].size() > 1) forbid_0[pos[i][0]] = 1;

    ASize = alphs.size();

    rep(i, 10) used[i] = 0;
    sum = 0;
    cout << dfs(0) << endl;

  }

  return 0;
}