ARC094 D - Worst Case - ferinの競プロ帳

考えたこと

よくわからないのでとりあえず実験する
A<=Bとか仮定しておくと便利そう
一回目、二回目に小さい順位を取った人が条件を満たすようにしたい
A=8,B=9 みたいなのが来たら下のように構成できて14個

1,71 71,1
2,35 35,2
3,23 23,2
4,17 17,4
5,14 14,5
6,11 11,6
7,10 10,7

x*(x+1) < ABとなるような最大のxを見つけると下のような構成ができる気持ちになる yは単調減少な列

1,y_1
2,y_2
 …
x,y_x

なので大体2x-2人になりそう
問題として A[i] <= x のときや y_j = B[i] のときをどう判定するか
B[i] = y_x みたいなときは B[i] = y_x - 1 とすれば条件を満たせそうな気がしたがy_(x-1) = y_x - 1みたいなときとかいろいろまずいケースがありそう
場合分けを頑張ったりするのかなあと思いいろいろ実験するがよくわからない -----(解説)http://kmjp.hatenablog.jp/entry/2018/04/07/0900を見た-----
2A-2人分は必ず達成できる
以下のように構成すればよい

1,A+B-1
2,A+B-2
  …
A-1,B+1

B+1,A-1
  …
A+B-2,2
A+B-1,1

A<=Bなので (A-x)(B+x) = AB + (A-B)x + x^2 < AB を満たす
上の構成の間である一回目で[A+1,B]位を取り二回目で[A,B-1]位を取る人の組で条件を満たす人が何人いるか
一回目で小さい順位を取った人にできるだけ大きな順位を当てた方がよさそう
したがって(A+1,A+x-1)(A+2,A+x-2)(A+3,A+x-3)…(A+x,A)みたいな組み合わせをしたい
x人全員のスコアがAB未満の条件を満たすような最大のxを求めたい
単調性がありそうなので二分探索をする
xの範囲は[0,B-A]
x人全員について判定をすると二分探索の判定部分の計算量がやばそう
冷静になって考えると (A+1)(A+x-1) が (A+x/2)^2 より大きくなることはなさそう
真ん中の部分だけ考えればいいので判定がO(1)でできる
まとめると 2A-2 + (二分探索で求めた人数) となる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int q;
  cin >> q;
  VI a(q), b(q);
  REP(i, q) {
    cin >> a[i] >> b[i];
    if(a[i] > b[i]) swap(a[i], b[i]);
  }

  REP(i, q) {
    // [lb, ub)
    int lb = 0, ub = b[i]-a[i]+1;
    auto check = [&](int mid) -> bool {
      for(int j=mid/2-2; j<=mid/2+2; ++j) {
        if(j<0 || b[i]-a[i]<j) continue;
        if((a[i]+j)*(a[i]+mid-j) >= a[i]*b[i]) return false;
      }
      return true;
    };
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(check(mid)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    cout << a[i]*2-2 + lb << endl;
  }

  return 0;
}