ARC094/ABC093 D問題を解いた

めっちゃ調べて、なるほどって言いながら解いた。
解いた問題はこれ
D - Worst Case。
解説がこれ
https://img.atcoder.jp/arc094/editorial.pdf。
解説はよくわからなかったので、これ
AtCoder ARC 094 D - Worst Case (700 点) - けんちょんの競プロ精進記録
を参考にして解いた。
これを読むと、元の解説でなんであんなことをしているかも理解できる。

解説

最大となる組み合わせは、1,2,...,xと1,2,...,xという頂点を逆順で組み合わせることで得られることが分かる。
途中に存在するであろうA, Bを飛ばす必要があるため、解答はx-1である。

1, 2, ..., x-1, x
x, x-1, ..., 2, 1

このとき、この最大値は

(x+1)//x * (x+1 - ((x+1)//2))

である。
感覚的に

x//2 * (x - x//2)

だと思っていたので、めっちゃ混乱した。

ここで、B = A + nであるとすると、最大はA*(A+(n-1))以上になることが分かる。
n >= 1であれば、（AとBが異なることに注意すると）積の最大値はA.Bを飛ばしても実現されることが分かる。

A=Bのときはよくわからない。
というわけで、そこは別で扱うことにする。

Q = int( input())
def matching(A,B):
    #最大となる組み合わせは、1,2,...,xと1,2,...,xという頂点を逆順で組み合わせることで得られることが分かる
    #このとき、これらの積の最大値は(x+1)//2*(x+1-(x+1)//2)である
    #ここで、B = A + nであるとき、最大はA*(A+(n-1))以上になることが分かる。
    #n >= 1であれば、積の最大値はA.Bを飛ばしても実現されることが分かる。
    if A == B:
        return 2*A - 2
    S = A*B
    L, H = 0, A*B
    while H - L != 1:
        M = (L+H)//2
        if ((M+1)//2)*(M + 1 - (M+1)//2) < S:
            L = M
        else:
            H = M
    return L-1 #L-1なのは、A,Bを飛ばすため
for _ in range(Q):
    A, B = map( int, input().split())
    print( matching(A,B))