abc 093 D. Worst Case (python)
最大マッチング問題というらしい。
解説を読んだら理解はしたけど
n= (a*b)**0.5 d = int(n) if n.is_integer(): d -= 1 ans = d*2-1
と
c= int((a*b-1)**0.5) chk = 2*c-1
が同じものになると思っていたので、間違え続けた。(例えば、(a, b) = 134576397, 134576399))
平方根を math.sprt で求めたが普通に **0.5 でいい気がする。
a や b を使わないといけない組はカウントに含めないので注意。
import math q = int(input()) for i in range(q): a,b = map(int,input().split()) if a == b: print(a*2-2) continue y = max(a,b) z = min(a,b) ind = math.sqrt(a*b) d = int(ind) if ind.is_integer(): d -= 1 cnt = 0 if d*(d+1) < a*b: if d >= z: cnt = 1 if d+1 >= y: cnt = 2 print(2*d-cnt) else: if d >= z: cnt = 1 print(2*d-1-cnt)