問題

http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/E.pdf
以下のような文脈自由文法( $CFG$ )が与えられる。

$Q ::= E=E$
$E ::= T\ |\ E+T\ |\ E-T$
$T ::= F\ |\ T*F$
$F ::= N\ |\ -F\ |\ (E)$
$N ::= 0\ |\ 1B$
$B ::= \epsilon |\ 0B\ |\ 1B$

これに沿って書かれた1つの等式を表す文字列 $S$ がある。各文字は '0', '1', '(', ')', '+', '-', '*', '=' で構成される。等式の一部または全部分は覆面算になっていて、同じ文字は同じアルファベット（大小区別しない）で表される。異なるアルファベットには、必ず異なる文字をあてはめる必要がある。条件を満たす文字のあてはめ方は何通りあるか。

$|S| \le 31$

解法

あてはめる文字が8通りしかないので、next_permutationであてはめる文字を全探索できる。構文解析は問題文中の $CFG$ を見てそのまま同じように再帰を実装すれば確実だが、下手だと下のようにコード量が多くなるので、実際はもっと手短に書くべきかもしれない。また、構文解析の途中に不適な構文となる場合があるが、それを失敗とみなすif文の処理がいくつも必要で書き忘れやすい。以下の1つ目のコードでは、不適な構文となった場合-infを返して、関数の戻り値を受け取るときは常に-infチェックをさせている。2つ目のコードのように例外を送出するようにすれば少し書きやすくなるが、1文字読み取るごとにtry{}catch(...){}して例外を繰り返し送出しているため、かなりパフォーマンスに差が出てしまう(ACはする)。

// 例外不使用 0.03sec (C++14)
string S;
int idx;
int N, M;
string alphas;
int curr;

bool consume(char c) {
  if(idx >= N) return false;
  if(S[idx] != c) return false;
  idx ++;
  return true;
}

int E();

int convert(string const& b) {
  int n = b.size();
  int ret = 0;
  for(int i=0; i<n; i++) {
    ret *= 2;
    assert(isdigit(b[i]));
    ret += b[i] - '0';
  }
  return ret;
}

string B() {
  string ret;
  while(1) {
    if(S[idx] == '0') ret += '0';
    else if(S[idx] == '1') ret += '1';
    else break;
    idx++;
  }
  return ret;
}

int Nu() {
  if(consume('0')) {
    return 0;
  }
  else if(consume('1')) {
    return convert("1" + B());
  }
  else {
    return -inf;
  }
}

int F() {
  if(consume('-')) {
    int r = F();
    if(r == -inf) return -inf;
    return -r;
  }
  else if(consume('(')) {
    int r = E();
    if(r == -inf) return -inf;
    if(!consume(')')) return -inf;
    return r;
  }
  else {
    return Nu();
  }
}

int T() {
  int num1 = F();
  if(num1 == -inf) return -inf;
  while(consume('*')) {
    int num2 = F();
    if(num2 == -inf) return -inf;
    num1 *= num2;
  }
  return num1;
}

int E() {
  int term1 = T();
  if(term1 == -inf) return -inf;
  while(1) {
    bool cont = 0;
    while(consume('+')) {
      cont = 1;
      int term2 = T();
      if(term2 == -inf) return -inf;
      term1 += term2;
    }
    while(consume('-')) {
      cont = 1;
      int term2 = T();
      if(term2 == -inf) return -inf;
      term1 -= term2;
    }
    if(!cont) break;
  }
  return term1;
}

bool Q() {
  if(idx == N) return curr == 0;

  int expr1 = E();
  if(expr1 == -inf) return false;

  if(!consume('=')) return false;

  int expr2 = E();
  if(expr2 == -inf) return false;
  if(expr1 != expr2) return false;

  return idx == N;
}

int main() {

  string T = "01+-*()=";
  sort(T.begin(), T.end());
  string RS; cin >> RS;
  N = RS.size();
  for(auto c: RS) if(isalpha(c)) alphas.push_back(c);
  sort(alphas.begin(), alphas.end());
  alphas.erase(unique(alphas.begin(), alphas.end()), alphas.end());
  M = alphas.size();

  if(M > T.size()) {
    cout << 0 << endl;
    exit(0);
  }

  int ans = 0;
  set<string> st;
  do {
    S = RS;
    rep(i, N)
      if(isalpha(S[i])) S[i] = T[alphas.find(S[i])];
    if(!st.count(S)) {
      st.insert(S);
      idx = curr = 0;
      ans += Q();
    }
  } while(next_permutation(T.begin(), T.end()));
  
  cout << ans << endl;

  return 0;
}

// 例外使用 0.80sec (C++14)
void consume(char c) {
  if(idx >= N) throw exception();
  if(S[idx] != c) throw exception();
  idx ++;
}
 
bool try_consume(char c) {
  try {
    consume(c);
  } catch(...) {
    return false;
  }
  return true;
}
 
int E();
 
int convert(string const& b) {
  int n = b.size();
  int ret = 0;
  for(int i=0; i<n; i++) {
    ret *= 2;
    assert(isdigit(b[i]));
    ret += b[i] - '0';
  }
  return ret;
}
 
string B() {
  string ret;
  while(1) {
    if(S[idx] == '0') ret += '0';
    else if(S[idx] == '1') ret += '1';
    else break;
    idx++;
  }
  return ret;
}
 
int Nu() {
  if(try_consume('0')) return 0;
  consume('1');
  return convert("1" + B());
}
 
int F() {
  if(try_consume('-')) {
    return -F();
  }
  else if(try_consume('(')) {
    int r = E();
    consume(')');
    return r;
  }
  else {
    return Nu();
  }
}
 
int T() {
  int num1 = F();
  while(try_consume('*')) {
    int num2 = F();
    num1 *= num2;
  }
  return num1;
}
 
int E() {
  int term1 = T();
  while(1) {
    bool cont = 0;
    while(try_consume('+')) {
      cont = 1;
      int term2 = T();
      term1 += term2;
    }
    while(try_consume('-')) {
      cont = 1;
      int term2 = T();
      term1 -= term2;
    }
    if(!cont) break;
  }
  return term1;
}
 
bool Q() {
  int expr1 = E();
  consume('=');
  int expr2 = E();
  return expr1 == expr2 && idx == N;
}
 
int main() {
 
  string T = "01+-*()=";
  sort(T.begin(), T.end());
  string RS; cin >> RS;
  N = RS.size();
  for(auto c: RS) if(isalpha(c)) alphas.push_back(c);
  sort(alphas.begin(), alphas.end());
  alphas.erase(unique(alphas.begin(), alphas.end()), alphas.end());
  M = alphas.size();
 
  if(M > T.size()) {
    cout << 0 << endl;
    return 0;
  }
 
  int ans = 0;
  set<string> st;
  do {
    S = RS;
    rep(i, N) {
      if(isalpha(S[i])) S[i] = T[alphas.find(S[i])];
    }
    if(!st.count(S)) {
      st.insert(S);
      idx = curr = 0;
      try { ans += Q(); } catch (...) {}
    }
  } while(next_permutation(T.begin(), T.end()));
   
  cout << ans << endl;
 
  return 0;
}

感想

はじめ「AOJ1161 Verbal Arithmetic の時間制限が厳しいバージョンか？」と勘違いしていたが、文字の種類数が8通り制約から実際はあてはめる文字の数に制限があったので特別枝刈りなどは不要な問題だった。

Logfiles

ICPCOOC2016 E: Infallibly Crack Perplexing Cryptarithm

問題

解法

感想