はじめに
皆さんはAtCoderで使用できる言語のversionは意識したことがあるでしょうか？
AtCoderに慣れるために過去問を解いていたところ、思わぬ落とし穴に落ちました。
今回は、version違いによるミスを書いていきます。
問題
今回の問題を以下に載せます。
C - Anti-Division
考え方
問題内容はシンプルで、整数$A～D$のうち、$A$以上$B$以下で、$C$でも$D$でも割り切れないものの個数を求めるという問題。
$A$以上$B$以下で、$C$でも$D$でも割り切れないものの個数を直接求めるよりは、$C$または$D$で割り切れる個数を、$A$以上$B$以下の個数から引くほうが簡単そうなのでその方法で行きます。
$C$または$D$で割り切れる個数は、$C$で割り切れる個数と$D$で割り切れる個数の合計から、$C$かつ$D$で割り切れる個数を引けば求められます。そのため、$C$と$D$の最小公倍数を求める必要があります。
実際に書いたコード
最小公倍数を求めるには、最大公約数を求める必要があります。調べてみると、Pythonには便利なことにmathモジュールにあるgcd()関数で最大公約数を求めることが出来ます。
書いたコードが以下になります。
from sys import stdin
import math
def lcm(x, y):
return (x * y) // math.gcd(x, y)
def main():
A, B, C, D = [int(x) for x in stdin.readline().rstrip().split()]
C_D_lcm = lcm(C, D)
z = B//C_D_lcm - A//C_D_lcm
if A % C == 0:
x = (B//C) + 1 - (A//C)
else:
x = (B//C) - A//C
y = B//D - A//D
print((B-A+1)-(x+y-z))
if __name__ == "__main__":
main()
結果
実際に提出してみると結果はRE。
おかしい。自分の環境では確かに動いたはず。
もう一度自分の環境で動かしてみると、
$ python3 C_Anti_Division.py
314159265358979323 846264338327950288 419716939 937510582
532105071133627368
正しく動きました。
REの原因はversion違い！
リファレンスで調べてみると、math.gcd()はversion3.5に追加されたみたいです。AtCoderのPythonはversion3.4.3なので、使用できないのです。
さらに調べていくと、version3.4以前はmathモジュールではなくfractionsモジュールにgcd()関数があるみたいです。
mathモジュールではなくfractionsモジュールに変更したところ、無事に通りました。
ちなみに、fractionsモジュールのgcd()はversion3.5から非推奨らしく、version3.7.3で使用するとmath.gcd()を薦めてきます。
$ python3 -V
Python 3.7.3
$ python3 C_Anti_Division.py
314159265358979323 846264338327950288 419716939 937510582
C_Anti_Division.py:6: DeprecationWarning: fractions.gcd() is deprecated. Use math.gcd() instead.
return (x * y) // fractions.gcd(x, y)
532105071133627368
#AtCoderで使用できる言語のversion
AtCoderで使用できる言語のversionはコンテストごとのルールに記載されています。
言語によっては使用できるライブラリ(Python3ではnumpy,scipy,scipy,C++ではBoostなど)があります。
また、コンテストによっては使えないものもあるので、参加する前にルールを確認したほうがいいかもしれません。
今回のコンテストで使用できる言語のversion一覧は以下になります。
https://atcoder.jp/contests/abc131/rules
まとめ
AtCoderと自分の環境を同じversionにしましょう。そうすればこのようなミスは起きません。
もし、今までversionを気にしずに解いていたのなら、このようなことが起こりえることを意識していただきたいです。