土下座しながら探索中

主に競技プログラミング

AOJ 1233 : Equals are Equals

問題リンク : Equals are Equals | Aizu Online Judge

問題概要 :
複数の数式が与えられる
一番最初の式が正しい答えで、その他の式がそれと同じかどうか判定せよ
細かい制約は略

解法 :
各変数に対してランダムに値を割り当て、式の結果が一致するかどうかチェックを行う
これを100回くらい行って全て一致していれば良いものとした
入力からとった式の適切な場所に*をつければただ構文解析するだけ

Kuala Lumpur でほぼ同じ問題があった
そっちもこんな感じでランダムの値を各変数に割り当てて解いた
一応、実際に変数のまま構文解析したコードも書いた

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

class Parsing{
private:
  string parse;
  int pos;
public:
  Parsing(string s){ parse = s, pos = 0; }

  ll fact(){
    if(parse[pos] == '('){
      pos++;
      ll p = expression();
      pos++;
      return p;
    }else{
      ll p=0;
      while('0' <= parse[pos] && parse[pos] <= '9'){
        p *= 10LL;
        p += parse[pos]-'0';
        pos++;
      }
      return p;
    }
  }

  ll pow(){
    ll p = fact();
    while( parse[pos] == '^' ){
      pos++;
      ll limit = fact();
      ll tmp = 1LL;
      rep(_,limit) tmp *= p;
      p = tmp;
    }
    return p;
  }
 
  ll term(){
    ll p = pow();
    while(parse[pos] == '*' || parse[pos] == '/'){
      if(parse[pos] == '*'){pos++;p *= pow();}
      else {pos++;p /= pow();}
    }
    return p;
  }
 
  ll expression(){
    ll p = term();
    while(parse[pos] == '+' || parse[pos] == '-'){
      if(parse[pos] == '+'){pos++;p+=term();}
      else {pos++;p-=term();}
    }
    return p;
  } 
 
};

inline bool isNum(char c) { return '0' <= c && c <= '9'; }
inline bool isVar(char c) { return 'a' <= c && c <= 'z'; }

bool isMulti(char a,char b,bool flag){
  if( flag && isNum(a) && isNum(b) ) return true;
  if( isNum(a) && isVar(b) ) return true;
  if( isVar(a) && isVar(b) ) return true;
  if( isVar(a) && isNum(b) ) return true;
  if( ( a == ')' ) && ( b == '(' ) ) return true;
  if( ( a == ')' ) && ( isNum(b) || isVar(b) ) ) return true;
  if( ( isNum(a) || isVar(a) ) && ( b == '(' ) ) return true;
  return false;
}

string Craftworks(string s){
  string ret = "",tmp = "";
  stringstream ss;
  ss << s;
  vector<string> buf;
  while( !(ss>>s).fail() ) buf.push_back(s);
  rep(i,buf.size()){
    if( i+1 < buf.size() && isMulti(buf[i][(int)buf[i].size()-1],buf[i+1][0],true) ) {
      tmp += ( buf[i] + "*" );
    } else tmp += buf[i];
  }
  rep(i,tmp.size()){
    if( i+1 < tmp.size() && isMulti(tmp[i],tmp[i+1],false) ) ret += string(1,tmp[i]) + "*";
    else                                                     ret += string(1,tmp[i]);
  }
  return ret;
}

const int MOD = 10;

string itos(int i) { stringstream ss; ss << i; return ss.str(); }

int main(){
  srand((unsigned int)time(NULL));
  string s;
  while( 1 ){
    vector<string> vec;
    while( getline(cin,s) ) {
      if( s == "." ) break;
      vec.push_back(s);
    }
    if( vec.empty() ) break;
    rep(i,vec.size()) vec[i] = Craftworks(vec[i]);

    vector<bool> verdict(vec.size(),true);

    rep(_,100){
      vector<string> value(26);
      rep(i,26) value[i] = itos(rand() % MOD + 1);
      vector<ll> result;

      rep(i,vec.size()){
        string buf;
        rep(j,vec[i].size()) {
          if( vec[i][j] == ' ' ) continue;
          if( 'a' <= vec[i][j] && vec[i][j] <= 'z' ) buf += value[vec[i][j]-'a'];
          else                                       buf += vec[i][j];
        }
        Parsing par(buf);
        result.push_back(par.expression());
        if( i ) verdict[i] = verdict[i] & ( result[i] == result[0] );
      }
    }
    REP(i,1,vec.size()) puts(verdict[i]?"yes":"no");
    puts(".");
  }
  return 0;
}