ARC094D: Worst Case

https://arc094.contest.atcoder.jp/tasks/arc094_b

本質は構成ゲーです。

A<=Bとしても一般性を失いません。
CをA*B>C^2を満たすうち最大の数とします。
A=A*Bのとき2*C-2、
C(C+1)=3であることがわかります。
なのでB-A<=2の時は個別にやればよいです。
B-A=0のとき2*A-2
B-A=1のとき2*A-2
B-A=2のとき2*A-1
となります。これで全ての場合がカバーできました。
しかしよく見ると、B-A=2の場合はB-A>=3の時と同じ扱いができるので、結局B-A=0,1,>=2の3通りについて考えれば良いことがわかります。

こういう問題はいい構築方法が思いつけば勝ちですね。
二分探索思いつくのが一番良かったんですが。

ll Q, A, B;

void solve() {
	cin >> Q;
	while(Q--) {
		cin >> A >> B;
		if(A > B) swap(A, B);
		if(B - A <= 1) cout << 2 * A - 2 << "\n";
		else {
			ll C = ll(sqrt(A * B) - eps);
			if(C * (C + 1) >= A * B) cout << 2 * C - 2 << "\n";
			else cout << 2 * C - 1 << "\n";
		}
	}
}