AtCoder Regular Contest #004 C: 平均値太郎の憂鬱

問題

ここ参照。

方針

本番中は二分探索をしていた。ほとんどのケースは通っていたのだけれど、いくつかのケースで落ちていた。分数が既約分数だと思い込んでいたけど、そうじゃない場合もあるようだ。おそらく落ちた原因はそれだと思う。
二分探索よりスマートでシンプルな解法があって、以下の2次不等式をiについて解けばよい。

平方根とか出てくるけど、マージンを取るような方向の近い整数に丸めるとよい。

ソースコード

view plainprint?

1. using namespace std;  
2.   
3. #define REP(i, n) for(int i=0; i<(int)(n); i++)  
4. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
5.   
6. long long gcd(long long a, long long b) {  
7.     if (!b)  
8.         return a;  
9.     return gcd(b, a%b);  
10. }  
11.   
12.   
13. int main() {  
14.     long long x, y;  
15.     char c;  
16.   
17.     cin >> x >> c >> y;  
18.     long long g = gcd(x, y);  
19.     x /= g;  
20.     y /= g;  
21.       
22.     bool res = false;  
23.     for (long long i = (2*x-y)/y/y; i <= (2*x+y)/y/y+1; i++) {  
24.         long long n = i*y;  
25.         long long sum = n*(n+1)/2;  
26.         long long m = sum - i*x;  
27.         if (1 <= m && m <= n) {  
28.             res = true;  
29.             cout << n << " " << m << endl;  
30.         }  
31.     }  
32.   
33.     if (!res)  
34.         puts("Impossible");  
35.     return 0;  
36. }  

using namespace std;

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

long long gcd(long long a, long long b) {
    if (!b)
        return a;
    return gcd(b, a%b);
}


int main() {
    long long x, y;
    char c;

    cin >> x >> c >> y;
    long long g = gcd(x, y);
    x /= g;
    y /= g;
    
    bool res = false;
    for (long long i = (2*x-y)/y/y; i <= (2*x+y)/y/y+1; i++) {
        long long n = i*y;
        long long sum = n*(n+1)/2;
        long long m = sum - i*x;
        if (1 <= m && m <= n) {
            res = true;
            cout << n << " " << m << endl;
        }
    }

    if (!res)
        puts("Impossible");
    return 0;
}