私はFind the minpythonを使用してfacebook hackercupの問題を解決していました.私のコードはサンプル入力に対しては正常に動作しますが、大きな入力（10 ^ 9）の場合、完了するまでに数時間かかります.
では、その問題の解が python を使用して 6 分以内に計算できない可能性はありますか? それとも、私のアプローチが悪すぎるのでしょうか?
問題文:
スマイリーを送信した後、ジョンは配列で遊ぶことにしました。ハッカーが配列をいじることを楽しんでいることをご存知ですか? John には、非負の整数mを含む0 から始まるインデックス配列 があります。nしかし、k彼は配列の最初の値しか知らず、残りを把握したいと考えています。
John は次のことを知っています: 各 indexiについて、ここでk <= i < n、は、 の以前の値に含まれていないm[i]最小の非負の整数です。*k*m
たとえばk = 3、n = 4と の既知の値が でmある場合[2, 3, 0]、彼はそれを理解できm[3] = 1ます。
ジョンは、世界をよりオープンでつながりのあるものにするために多忙を極めているため、配列の残りの部分を把握する時間がありません。彼を助けるのはあなたの仕事です。
の最初のk値をm指定して、この配列の n 番目の値を計算します。（つまりm[n - 1]）。
nとの値はk非常に大きくなる可能性があるため、疑似乱数ジェネレーターを使用して の最初のk値を計算しますm。正の整数a、b、cおよびが与えられるとr、 の既知の値はm次のように計算できます。
m[0] = a
m[i] = (b * m[i - 1] + c) % r, 0 < i < k
入力
最初の行には、テスト ケースの数である整数 T (T <= 20) が含まれます。
これに続いて、それぞれ 2 行からなる T 個のテスト ケースが続きます。
各テスト ケースの最初の行には、スペースで区切られた 2 つの整数 ,
n(k,1 <= k <= 10^5)が含まれk < n <= 10^9ます。各テスト ケースの 2 行目には、スペースで区切られた 4 つの整数
a,b,c,r(0 <= a, b, c <= 10^9, 1 <= r <= 10^9) が含まれます。
2 つのアプローチを試しましたが、どちらも 6 分で結果を返すことができませんでした。これが私の 2 つのアプローチです。
最初：
import sys
cases=sys.stdin.readlines()
def func(line1,line2):
n,k=map(int,line1.split())
a,b,c,r =map(int,line2.split())
m=[None]*n #initialize the list
m[0]=a
for i in xrange(1,k): #set the first k values using the formula
m[i]= (b * m[i - 1] + c) % r
#print m
for j in range(0,n-k): #now set the value of m[k], m[k+1],.. upto m[n-1]
temp=set(m[j:k+j]) # create a set from the K values relative to current index
i=-1 #start at 0, lowest +ve integer
while True:
i+=1
if i not in temp: #if that +ve integer is not present in temp
m[k+j]=i
break
return m[-1]
for ind,case in enumerate(xrange(1,len(cases),2)):
ans=func(cases[case],cases[case+1])
print "Case #{0}: {1}".format(ind+1,ans)
2番：
import sys
cases=sys.stdin.readlines()
def func(line1,line2):
n,k=map(int,line1.split())
a,b,c,r =map(int,line2.split())
m=[None]*n #initialize
m[0]=a
for i in xrange(1,k): #same as above
m[i]= (b * m[i - 1] + c) % r
#instead of generating a set in each iteration , I used a
# dictionary this time.
#Now, if the count of an item is 0 then it
#means the item is not present in the previous K items
#and can be added as the min value
temp={}
for x in m[0:k]:
temp[x]=temp.get(x,0)+1
i=-1
while True:
i+=1
if i not in temp:
m[k]=i #set the value of m[k]
break
for j in range(1,n-k): #now set the values of m[k+1] to m[n-1]
i=-1
temp[m[j-1]] -= 1 #decrement it's value, as it is now out of K items
temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1 # new item added to the current K-1 items
while True:
i+=1
if i not in temp or temp[i]==0: #if i not found in dict or it's val is 0
m[k+j]=i
break
return m[-1]
for ind,case in enumerate(xrange(1,len(cases),2)):
ans=func(cases[case],cases[case+1])
print "Case #{0}: {1}".format(ind+1,ans)
2 番目のアプローチの最後の for ループは、次のように書くこともできます。
for j in range(1,n-k):
i=-1
temp[m[j-1]] -= 1
if temp[m[j-1]]==0:
temp.pop(m[j-1]) #same as above but pop the key this time
temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1
while True:
i+=1
if i not in temp:
m[k+j]=i
break
サンプル入力:
5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46
出力：
Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12
私はすでにcodereviewを試しましたが、まだ誰も答えていません。