SRM 483 Div2 Hard BestApproximationDiv2

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11073&rd=14236

1未満の小数numberが与えられる。A / Bとnumberの、整数部から連続して一致する桁数がもっとも長くなるような自然数A、Bを探せ。ただし分母の最大値はmaxDen以下で、答えが複数あるときは分母、分子の順で最小のものを返せ。

問題文が長いだろ・・・

やりかた

全探索ではTLE。
ある分母Bを固定したとして、A / Bがnumberの最も良い（題意上の）近似になる時、AはA ≒ number * Bなので、

(int)number * B - 1 か (int)number * B か (int)number * B + 1

のいずれかになる。なので分母Bをループで回す。各分母で試す分子は上の３通りを試せばいい。制約上割り算は50桁まで行わねばならないのでここは要実装。

class BestApproximationDiv2 {
public:
  double stoi(string s){
    stringstream ss;
    ss << s;
    double a;
    ss >> a;
    return a;
  }

  /* int to string */
  string itos(int a){
    stringstream ss;
    ss << a;
    return ss.str();
  }

  char strA[60];
  /* a/bの結果をn桁までstrAにつめる */
  void divStr(ll a, ll b, int n){
    int i;
    for(i = 0; i < n ; i++){
      strA[i] = '0' + a / b;
      a %= b;
      a *= 10;
    }
    strA[i] = '\0';
    return;
  }
  string findFraction(int maxDen, string number) {
    string result;
    double C = stoi(number);
    string num;
    for(int i = 0; i < (int)number.length(); i++) 
      if(number[i] != '.') num += number[i];
    
    int coins = 0;
    for(ll B = 1; B <= maxDen; B++){
      ll tmp = B * C;
      for(ll candA = max(0LL, tmp - 2); candA <= tmp + 2 && candA < B; candA++){
	int cnt = 0;
	divStr(candA, B, 50);
	for(; cnt < (int)num.length() && strA[cnt] != '\0' && num[cnt] == strA[cnt]; cnt++);
	
	if(coins < cnt){
	  coins = cnt;
	  result = itos(candA) + "/" + itos(B) + " has " + itos(cnt) 
	    + " exact digits";
	}
      }
    }
    return result;
  }
};

割り算結果をstringに詰めて返して計算していたらどう頑張ってもTLEだった。静的なchar配列に放り込んだら通った。stringは遅い。はっきりわかんだね。