AGC041

AGC041に参加しました。

結果は0完。。。

A問題

方針としてはAとBの差が
偶数の時は、お互いに近づけばいいだけなので差分を2で割った商が答えで、
奇数の時はA,Bの近い方の端っこに行ってA,Bの差分を偶数に調整してからお互い近づけば良いので

公式の解答にある通り

$$ min(A-1, N-b) + 1 + \frac{b-a-1}{2} $$

が答えになります。
ここまでわかった。

が、通らなかった。

以下が通らなかったコード

n, a, b = (int(i) for i in input().split())

x = b-a
if ((x % 2) == 0):
    print(int(x/2))
    exit()
else:
    print(min(a-1, n-b) + int((x+1)/2))
    exit()

何が悪かったか？

int(x/2)が問題でした。

これよく言ってる人いるけど、int(n/2)だと、n/2が浮動小数演算になっちゃうので、nが大きい時に精度が＞＜
nに(10^18 - 1)とかを入れて試すとわかりやすいです！https://t.co/jSOFSgdlgO

— chokudai(高橋 直大)🍆🍡 (@chokudai) December 28, 2019

なるほど。
それで、数が大きいと除算演算子/が精度が悪くなるのはわかったけど、どこまで大きいくなると精度が落ちるのか？

倍精度浮動小数点では、64ビットを使って数を表現し、その内訳は次のとおりである。

符号ビット (sign): 1 ビット
指数部 (exponent): 11 ビット
仮数部 (fraction): 52 ビット
精度を求める上で重要なのは仮数部のビット数 = 52ビットである。これに加えて、「最上位ビットは1に決まってるんだから書かなくてもいいでしょ、省略するわ」という省略された1ビット（ケチ表現）がある。合計53ビットがdouble型の精度となり、10進に直した精度は53 * log10 2 =15.95桁となる。

つまり、float型の精度は約16桁である。これより高い精度は表現できない。
https://linus-mk.hatenablog.com/entry/2019/05/26/234642

16桁くらいまでしか精度を保てないとのことでした。

ということで、除算結果を不動小数点にしない//で切り捨て除算を行えばOK

以下が通ったコード

n, a, b = (int(i) for i in input().split())
 
x = b-a
if ((x % 2) == 0):
    print(x//2)
    exit()
else:
    print(min(a-1, n-b) + (x+1)//2)
    exit()

感想

計算精度の話大学の授業でやったなぁ。。。