Python Atcoder 最大値から計算量を落とす

本日も、競技プログラミングを学習していく上で、

「この考え方大事だな」と思ったことについて記事にしていきたいと思います。

皆さんの学習の助けになったら、幸いです。

本日のトピック

そもそも計算量って

計算量とは、「アルゴリズムの計算効率や問題の難しさを測るための尺度」のことです。Atcoder、特にPythonではC問題以降の問題では、すごく重要な考えです。
Pythonは1秒あたりの実行可能オーダーは、10**7までです。ABC問題では実行時間の制限が2secなので、基本的に10**8オーダー以上の計算量だと【TLE】（時間かかり過ぎ）でエラーになります。

では、どうやったら計算量が落とせるのか？　を問題を通して学習していきましょう。

良問題 -193C- Unexpressed- から

例題は、Atcoder ABC 193の　C問題 Unexpressedから使用させていただきます。問題文↓

今回大事なのは、Nのオーダーが10**10だと言うこと。

先程も明記しましたが、Pythonは1秒あたりの実行可能オーダーは、10**7までです。　なので今回は、2から10**10までをfor文で回すことができません。

ではどうすれば良いでしょうか？

a,bの最大値について考えましょう。

今回は、a,bの最大値について考えましょう。

a**b =< N =< 10**10 なので、
a**b =10**10　ここから、aとbの最大値について考えてみましょう

aの最大値

b = 2 の時、aは最大値をとります。

a **2 = 10**10
a = 10**5

よって、aの最大値は10**5です。

次にbの最大値について考えます。

ｂの最大値
a = 2 の時、bは最大値をとります。計算式が少し複雑ですが、

2**b = 10**10
b log(2) = 10 log(10)
b = 10{ log(10) / log(2) }
b = 10 * 3.333・・
b <= 34

なので、b の最大値は34です。

上記のことから、計算量は
10**5 * 34　＜　10**10　にできます！

実際のコード

N = int(input())
Settable = set()
# 2<a<10**5, 2<b<34なので
for a in range(2, 10**5 + 1):
   for b in range(2, 34):
       if a**b <= N:

           Settable.add(a**b)
amount = N-len(Settable)
print(amount)

上記のコードなら、TLEになることなく、コードを通すことができます。

終わりに

Atcoderをやる上で、計算量はすごく大事な要素になります。自分もまだまだ勉強途中なので、間違っているところがあったら、コメントお願いします！！