pythonの整数処理の落とし穴
こんにちは。株式会社Rosso、AI部です。
最近AtCoderを始めたのですが、たまにpythonの整数処理でひどい目に遭うので、危険な処理をいくつか調べてみました。
小数点以下切り捨て a//x
math.floor(a/x)は使わない。
a = 12709666153793987
x = 36
print(math.floor(a/x))#353046282049833
print(a//x) #353046282049832
a が10**16を超えたあたりからmath.floor(a/x)だと誤った答えが出てくる。
くらいで失敗する。
AtCoderだと1問でもWAだとダメなのでa//x のみを推奨。
小数点切り上げ -(-a//x)
math.ceil(a/x) を使うと失敗する
-(-a//x)を使う
(a+x-1)//xでもOK
a = 690458448255264703
x = 143
print(math.ceil(a/x))#4828380757029823
print(-(-a//x)) #4828380757029824
print((a+x-1)//x) #4828380757029824
aが10**16を超えたあたりから先のfloorと同じくらいの割合で失敗する。
上記の方法で処理しないと解けない問題
ARC135 A - Floor, Ceil - Decomposition
https://atcoder.jp/contests/arc135/tasks/arc135_a
以下のようにmath.floor,math.ceilを使ってしまうと7問WAとなってしまう
import math
mod = 998244353
def f(X):
if X in memo:
return memo[X]
if X <= 4:
return X
a = math.floor(X/2)
b = math.ceil(X/2)
memo[X] = f(a)*f(b)%mod
return memo[X]
X = int(input())
memo = {}
print(f(X))
以下のようにX//2,-(-X//2)を使うとACが取れる。
mod = 998244353
def f(X):
if X in memo:
return memo[X]
if X <= 4:
return X
a = X//2
b = -(-X//2)
memo[X] = f(a)*f(b)%mod
return memo[X]
X = int(input())
memo = {}
print(f(X))
番外編:四捨五入
AtCoderで四捨五入で困ったことは多分ないが、調べてみました。
ググるとpythonで四捨五入はround()と出てくる事が多いが、我々の思う四捨五入とは違う処理を行う。
n = 100.5
print(round(n)) #100
roundはそもそも四捨五入の関数じゃなくて偶数への丸めという処理とのこと。
Decimalという標準モジュールを使っても、ちゃんと四捨五入してくれるらしいがいろいろめんどくさい。
from decimal import Decimal,ROUND_HALF_UP
a = 100.50000000
Decimal(str(a)).quantize(Decimal("1"), rounding=ROUND_HALF_UP)
#101
int((n*2+1)//2) で桁数が10**9くらいまででは多くの場合は上手くいく。
n = 100.5000000000000000000001
print(int((n*2+1)//2)) #101
しかし、桁数が多くなってくるとfloatだと桁落ちしてしまう。
from decimal import Decimal,ROUND_HALF_UP
print("(n*2+1)//2"," Decimal")
for i in range(8,20):
n = 10**i + 0.500000
a = int((n*2+1)//2)
d = Decimal(str(n)).quantize(Decimal("1"), rounding=ROUND_HALF_UP)
# print(i,n)
print(a," ",d)
"""
(n*2+1)//2 Decimal
100000001 100000001
1000000001 1000000001
10000000001 10000000001
100000000001 100000000001
1000000000001 1000000000001
10000000000001 10000000000001
100000000000001 100000000000001
1000000000000001 1000000000000001
10000000000000000 10000000000000000
100000000000000000 100000000000000000
1000000000000000000 1000000000000000000
10000000000000000000 10000000000000000000
"""
Decimalのみで処理を完結させ、有効数字上限を解放することで高い桁数で正しく四捨五入が行えるようにはなる。
from decimal import Decimal,getcontext
#この設定で有効数字を増やせる
getcontext().prec = 51
for i in range(16,50):
n = 10**i
d = Decimal(str(n)) + Decimal("0.5") #10000~(省略)~00.5
d = d.quantize(Decimal("1"), rounding=ROUND_HALF_UP)
print(d)
"""
10000000000000001
100000000000000001
1000000000000000001
10000000000000000001
100000000000000000001
1000000000000000000001
10000000000000000000001
...
10000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000001
1000000000000000000000000000000000000000000000001
10000000000000000000000000000000000000000000000001
"""
ただ、恐らくこのような処理が必要になるような問題はAtCoderには出ない(出ないでほしい)。
番外編:マイナスを含む小数点以下切り捨て除算
どちらも正の場合はいつものa//xで切り捨て除算が可能だが、
マイナスでも切り捨て除算して欲しいことも。
だが、どちらかがマイナスの場合、pythonでは
print(8//7) # 1
print(-8//7) #-2
print(8//-7) #-2
print(-8//-7)# 1
と、マイナスの絶対値が大きくなる方向に切り捨てされてしまう。
-8の7での切り捨て除算でも-1にしてほしい場合、
C言語の場合は単に -8 / 7 で-1になるが、
いろいろ試してみた結果、pythonの場合は
def minus_floor(i,j):
return i // j + (i * j < 0) * (i % j != 0)
で上手くいく。
def minus_floor(i,j):
return i // j + (i * j < 0) * (i % j != 0)
a = 8285
x = 731
print("正のみ\n",a//x)
print("いつもの切り捨て除算でそのまま実行\n",-a//x,
a//-x,
-a//-x,)
print("マイナスに対応した切り捨て除算\n",
minus_floor(-a,x),
minus_floor(a,-x),
minus_floor(-a,-x))
"""
正のみ
11
いつもの切り捨て除算でそのまま実行
-12 -12 11
マイナスに対応した切り捨て除算
-11 -11 11
"""
「こうすればマイナスでも切り捨て除算ができます!!」とは、胸をはって言えないようなコードなので、
AtCoderが上手い人はマイナスのある切り捨て除算をする必要がないような解法を見つけているかもしれない。
(使うことがありませんように)