競技プログラミングの桁数と計算量について

Question

pythonの話です。
bitsetは桁がいくら大きくなろうと計算量がO(1)という事に一応なっていますよね?
でも一方で、https://atcoder.jp/contests/arc050/tasks/arc050_c
この問題のように、あまりにも膨大な桁数になったら処理に時間がかかるようなので、そこのところがどのような仕様なのか、もしわかる人いたら教えて欲しいです。。

Comments

[maisumakun]

O(1)は、「何に関する」計算量ですか？

[hayataka2049]

bitsetという言葉はちょっと聞き慣れないのですが、何でどういうことをするのを想定していますか？　C++など他の言語なら同名のパッケージやクラス等があるようですが、Pythonには見当たりませんし。

[Zuishin]

エスパーを待ってるんですか？

あなたの抱えた問題に回答できる人はいても、あなたがその人に問題を伝えることができなければ、回答は難しいと思いませんか？

常識で考えて、膨大な桁数の演算を定量時間で処理することはできません。「一応なっていますよね？」が間違っていると思います。桁数を n とした O(n) ではないかどうか、その情報ソースを確かめてください。

Answer 1

bitsetは桁がいくら大きくなろうと計算量がO(1)

O(1)ではなくO(N)です。ただ、C++でいうvector<bool>などと比べて約64倍ほど早くなります(厳密には異なります)。
参考: https://kimiyuki.net/blog/2017/06/07/bitset-vector-bool/