C-merのブログ

ザ・雑記

三年目の初学者(8問目)

問題
AtCoder Beginner Contest 093 D - Worst Case
D - Worst Case

使用言語
C++

方針
・100マス計算の表みたいな感じで行けるものだと思っていたが、細かいところができない。
・解説(https://img.atcoder.jp/arc094/editorial.pdf)を参考にした。下の通りに考えると判りやすい。(丸が最大となるときの候補の一つ)

f:id:C-mer:20180408200537j:plain
f:id:C-mer:20180408201622j:plain
f:id:C-mer:20180408201712j:plain

所感
・簡単そうに見えて難しそうなやつだと思ったら、やっぱりそうだった。
・実装はクソ楽。
・結構力作の解説のつもり。
・桁落ち、負の処理、根号の処理を気をつけたい。

コード

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

typedef long long ll;
typedef unsigned long long ull;

void solve(ll a, ll b)
{
  if (a > b) swap(a, b);
  //常に a <= b

  if (b - a <= 1) {
    cout<<2 * (a - 1)<<endl;
  } else {
    ll c = (int) sqrt(a * b);
    if (c * c == a * b) c--;

    if (c * (c + 1) >= a * b) {
      cout<<2 * (c - 1)<<endl;
    } else {
      cout<<2 * c - 1<<endl;
    }
  }
}


int main(){
  int q;
  cin>>q;

  ll a[q], b[q];
  REP(i,q) cin>>a[i]>>b[i];

  REP(i,q) solve(a[i], b[i]);

  return 0;
}