見出し画像

pythonの整数処理の落とし穴

株式会社Rosso公式note

こんにちは。株式会社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が上手い人はマイナスのある切り捨て除算をする必要がないような解法を見つけているかもしれない。
（使うことがありませんように）