ARC109

1完でした。ナイタ

A - Hands

a, b, x, y = MI()
 
d = abs(b - a)
 
ans = 0
if a < b:
    if y < 2*x:
        ans = d * y + x
    else:
        ans = 2 * d * x + x
elif a == b:
    ans = x
else:
    if y < 2*x:
        ans = (d-1)*y + x
    else:
        ans = (d-1)*2*x + x
 
print(ans)

B - log （解説）

誤差を考えたことなくて、何が間違ってるのかずーっと分からないまま時間切れになってしまった。

「$ k(k+1)/2\le n+1 $ を満たす最大の k を二分探索する」のが解説。

平方根の誤差に注意する必要がある。自分はDecimalを使ったが、二分探索をするのが一般的っぽいので、そのコードも書いた。

Decimal を使ったコード

$ k(k+1)/2\le n+1 $ から直接答えを計算する

n = I()
 
from decimal import Decimal
 
x = Decimal(str(8*n+9))**Decimal("0.5")
d = (-1 + x) // 2
 
print(n - d + 1)

二分探索を使ったコード

こっちのほうが良いカンジですね

n = I()
 
# 1 ~ n + 1 の中から k(k+1)/2 <= n+1 を満たす最大の k を求めたい
l = 1
r = n + 1
while r - l > 1:
    m = (l + r) // 2
    if m * (1 + m) // 2 <= n + 1:
        l = m
    else:
        r = m
    # print(l, r)
print(n - l + 1)