17 全探索2 Dif:379 ABC193 C：「AtCoder 凡人が『緑』になるための精選50問詳細解説」サンプル

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/677ec26921f08586dd18
次：https://qiita.com/sano192/items/002198d775b77e04cb40

【目標】
・計算量を見積もって全探索が間に合うか判断できるようになる
・setを使えるようになる

【概要】
少し工夫が必要だが、基本的には「全部試す」で解ける問題。
全探索で解けるかを考えるときはまずどれくらいの計算量なのかを見積もることが必要だ。この問題で計算量の見積もり方を学ぼう。

【方針】
1,2,3,...についてa^bで表せるか判定していく、という方法はうまくいかない。
逆にa^bで表せる数を数え、それをNから引くという方法を考えよう。

aを固定して考えると
a=2
b=2:2^2=4
b=3:2^3=8
b=4:2^4=16
…
a=3
b=2:3^2=9
b=3:3^3=27
b=4:3^4=81
…
というように表せる数を順に作ることができる。
a^bがNを超えるまでbを2,3,4,...と増やしていけばよい。

ではa^bを順に作っていく場合、計算量はどうなるか。
制約は1<=N<=10^10。
a=2のときはb=34、つまり2^34=17179869184>10^10となるからb=2~33まで計算すれば十分。
aの範囲は2<=a<=10^5でよい。なぜならaが10^5を超えた場合、bが最小の場合つまりb=2でも10^10を超えてしまうからだ。

つまり計算が必要な範囲は
a=2~10^5
それぞれのaに対して
b=2~33
となり、
計算量は10^5*32程度で間に合う。
(実際にはaが大きくなるとbの最大値は小さくなるので計算量はもっと少ない)

【実装】
入力を受け取る。

N=int(input())

次に「作れる数のセット」を作る。名前はable_num。

able_num=set()

setはリストのようなものだが、リストと違い、重複する値を入れることができない。
たとえばable_numに2^4=16が入っている時に4^2=16を追加しても16が2つ入ることはない。

a^bをaが小さい方から順に作っていく。
・a^b<=Nの場合
able_numに追加。
setはappendではなくaddで要素を追加することに注意。
・そうでない(N<a^b)場合
それ以上大きなbを確認する必要はないので次のaに進む=break。

for a in range(2,10**5+10):
    for b in range(2,1000):
        if a**b<=N:
            able_num.add(a**b)
        else:
            break

「for a in range(2,10**5+1):」でよいのでは？(aの範囲は2~10^5でよいのでは？)
と思った人は正しい。aは最大でも10^5まででよいからだ。
しかしギリギリを狙って書くと何か勘違いがあった時に余計なWA(不正解)がでてしまう。そのためTLE(実行時間制限超過)しない程度にaの探索範囲を広めにとっている。

「for b in range(2,1000):」
についても同様。bの範囲は2~33でよいから
「for b in range(2,34):」
で問題ない。しかし余計なWA(不正解)がでないよう、てきとうに大きめな数=1000まで探索範囲を広げている。

最後に「作れる数」の数をNから引いて出力すれば終わりだ。
setもリスト同様要素の数はlen(セット)で参照できる。

print(N-len(able_num))

【コード全文】

N=int(input())

able_num=set()

for a in range(2,10**5+10):
    for b in range(2,100):
        if a**b<=N:
            able_num.add(a**b)
        else:
            break

print(N-len(able_num))

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/677ec26921f08586dd18
次：https://qiita.com/sano192/items/002198d775b77e04cb40