AtCoder Regular Contest 129 SmallerXOR がTLEになる理由について

Question

AtCoder初心者です。
11月21日に行われました、AtCoder Regular Contest 129 のA問題であるSmallerXORについて、下記のようにビット演算子^を用いて計算を行ったところ、タイムアウト(TLE)判定となりました。

使用言語はPythonということで、for文を1回のみ使うように書きましたが、それでもTLEとなる理由がわかりません。
これは入力される範囲(L,R)の内、Rの値が大きければ大きい程、計算の試行回数も増加するためでしょうか？

————実際の問題—————

————入力したコード————

def XOR(x,N):
	return x^N

N, L, R = map(int, input().split())

ans = 0
for i in range(L, R+1):
	if XOR(i, N) < N:
		ans += 1
print(ans)

問題のURL
https://atcoder.jp/contests/arc129/tasks/arc129_a

よろしくお願い申し上げます。

Comments

[melian]

Intel Core i5 CPU(3.0 GHz)/Python 3.9 で L = 1, R = 10e+8 で実行してみると、完了までに 14 秒程度かかります。全数比較ではダメで、何らかのアルゴリズム(?)が必要ということなのでしょう。

[genkinaoko]

計算量まで調べて頂きありがとうございます。
やはりアルゴリズムを使用する必要があるのですね、、、
勉強になりました！

Answer 1

melianさんが書かれているとおり、競技プログラミングはアルゴリズムを考えるのが重要です。

アルゴリズムの説明をするのは大変ですので、コードだけ載せておきます。コードをよく読んでアルゴリズムを理解してください。

これで性能は格段に良くなるはずです。

def decomp(n):
    for i in range(64):
        if 1<<i > n:
            return i-1, n - (1<<(i-1))

def count_2p(p, N):
    return N&((1<<p)-1)

def count_one(L, N):
    p, off = decomp(L)
    return count_2p(p, N) + (off*((N>>p)&1))

def count(L, R, N):
    return count_one(R+1, N) - count_one(L, N)

実行例

>>> def check(L, R, N):
...     ans = 0
...     for i in range(L, R+1):
...         if XOR(i, N) < N:
...             ans += 1
...     return ans
...
>>> count(3,20,111)
13
>>> check(3,20,111)
13

Comments

[genkinaoko]

コードまで書いて頂きありがとうございます。
私にとって少し難解ではありますが、アルゴリズムの勉強の良い機会と思って
学ばさせて頂きます！