ARC094 D - Worst Case -

問題

D - Worst Case

解法1

公式解説通り

#include <bits/stdc++.h>
using namespace std;

using Int = long long;

int main() {
    Int Q;
    cin >> Q;
    while ( Q-- ) {
        Int A, B;
        cin >> A >> B;
        if ( A > B ) swap(A, B);
        
        if ( B - A <= 1 ) cout << 2*A-2 << endl;
        else {
            Int C = (Int)sqrt(A*B);
            if ( C*C == A*B ) C--;
            if ( C*(C+1) >= A*B ) cout << 2*C-2 << endl;
            else cout << 2*C-1 << endl;
        }
    }

    return 0;
}

解法2

dohatsuさん解
高橋君よりスコアの小さい参加者の人数を二分探索で求める。
そのために、N人を参加者の人数にできるかという、部分問題を考える。

例として、A = 5, B = 10, N = 12の場合を考える。
1回目の他の参加者の候補として、
1 2 3 4 6 7 8 9 10 11 12
２回目の他の参加者の候補として、
1 2 3 4 5 6 7 8 9 11 12
が考えられる。
参加者の人数をできるだけ多くするためには、
(1, 12) (2, 11) ... (12, 1)
のようにするのがいいことが分かる。(積をいい感じに少なくするため(証明はしてない))

凸関数になっていそうなので、真ん中あたりの値だけ確認すればいい。
(a, b) という組み合わせがあったとき、ab >= AB を１つでも満たしてしまったら、Nは答えとして採用できない。
真ん中を適当に100個ぐらい見れば多分十分。

以上のことが分かれば、二分探索で解くことができる。

感想

sqrt(A*B)付近になることは分かったんだけど、そこからWAが取れなかった。
こういう問題を論理的に考えて解けるようにしたい。