ferinの競プロ帳

競プロについてのメモ

ARC094 D - Worst Case

問題ページ
D - Worst Case

考えたこと

  • よくわからないのでとりあえず実験する
  • 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;
}