SRM 483 div2 hard: BestApproximationDiv2

問題

TopCoder Statistics - Problem Statement

解法

mayokoex.hatenablog.com

さっきとほとんど同じです。今度は maxDen の値が大きいので, B を決めた後の A の範囲をある程度絞り込みます。
A の値はだいたい B*number となっているのが良いので, B*number ± 5 程度の範囲を調べれば良いでしょう。

ただ結構時間制限が危なかったので想定解は ± 1 なのかもしれないです。

const int offset = 5;

class BestApproximationDiv2 {
public:
    string findFraction(int maxDen, string number) {
        string s;
        for (char c : number) if (c != '.') s += c;
        int n = number.size();
        double d = 0;
        for (int i = n-1; i >= 2; i--) {
            d = d + (number[i]-'0');
            d /= 10;
        }
        int bestA = -1, bestB = -1, best = 0;
        for (int B = 1; B <= maxDen; B++) {
            int minA = B*d;
            minA = max(0, minA-offset);
            for (int A = minA; A < min(minA+2*offset, B); A++) {
               ll a = A, b = B;
                string t;
                for (int i = 0; i < n-1; i++) {
                    t += (char)(a/b + '0');
                    a -= (a/b)*b;
                    a *= 10;
                }
                int score = 0;
                for (; score < n-1; score++) {
                    if (t[score] != s[score]) break;
                }
                if (score > best) {
                    best = score;
                    bestA = A;
                    bestB = B;
                }
            }
        }
        string ans = to_string(bestA) + "/" + to_string(bestB) + " has " + to_string(best) + " exact digits";
        return ans;
    }
};