N,K,Q = map(int,input().split())
A = [int(input()) for _ in range(N)]
A.insert(K,Q)
for a in A:
print(a)
N,K = map(int, input().split())
A = [int(input()) for _ in range(N)]
flag = 'NO'
for a in A:
if a == K:
flag = 'YES'
break
print(flag)
よく考えたら、前にもリストの中にKがなかったらというのがありましたね。。。
忘れてました。それさえあれば下記の様に短くできますね
N,K = map(int, input().split())
A = [int(input()) for _ in range(N)]
print("YES" if K in A else "NO")
N,Q = map(int,input().split())
A = [int(input()) for _ in range(N)]
B = [int(input()) for _ in range(Q)]
for b in B:
print('YES' if b in A else 'NO')
これもこれでOK!と思ったら、、、
最後のケースが膨大なとき、タイムオーバーでだめでした。
回答を見ると、これが計算量と言われるジャンルらしく
(クエリの次が計算量という分野でした)
というわけで別の方法を探さないといけないと。
で、どうするかというと、Aは順番はなくてもよいので集合にして、
あとはそのまま計算。という。
N,Q = map(int,input().split())
A = {int(input()) for _ in range(N)}
for _ in range(Q):
print('YES' if int(input()) in A else 'NO')
N = int(input())
A = [int(input()) for _ in range(N)]
A.pop(0)
#上の行は下のように書いても良い
del A[0]
for a in A:
print(a)
N,K = map(int, input().split())
A = [int(input()) for _ in range(N)]
for _ in range(K):
if input() == 'pop' and len(A) > 0:
del A[0]
else:
for a in A:
print(a)
これでもいいんですが、計算量を意識しないと量が大きくなったときに駄目になると。
テスト4が0.64秒と他のケースより時間がかかるので、これを短くすると考える。
配列は1個消すたびに、配列を移動させないといけないので時間がかかる。
と解答の説明には書いてあるのだけど、
配列というのは箱のようなものでその一つ一つに要素をいれているようなもの。
で、最初の要素を消すたびに2番目の要素を1番目の箱に、3番目の要素を2番目の箱に、、、と全部移動させないといけない、、、とイメージすれば良い。
でそれを解決するために両端キューというのがあるらしい。
これは末尾への要素の追加と先頭要素の削除を高速(O(1))に行うことができる、と説明されているのだが、
前にもキューというのを習ったんだけど、
キューというのは両端が開いているイメージのデータ構造になっていて
enqueはおしりに数値を入れ、
dequeは頭から数値を取り出していくという感じ
...という風に習った。
dequeだけあればよいので
from collections import deque
N,K = map(int, input().split())
#これをdequeにする
A = deque([int(input()) for _ in range(N)])
for _ in range(K):
if input() == 'pop' and len(A) > 0:
#頭から削除
A.popleft()
continue
#ちなみにelseする必要はなく、popでなかったらもうskipしてしまえばよい
for a in A:
print(a)
ケース4は0.64秒⇒0.24秒になりました。短いな。
ちなみに他にも解法があって、削除したことにして+1要素を進めるという方法もある
なるほど!
N,K = map(int, input().split())
A = [int(input()) for _ in range(N)]
f = 0
for _ in range(K):
if input() == 'pop':
f += 1
continue
for i in range(f,N):
print(A[i])
ケース4は0.64秒⇒0.27秒になりました。ちょっと解法1には負けるけどそれでも
短くなってますね。
たしかに箱を移動しなくても良いしね。
これが計算量というやつですね。。。勉強になりました。
今日はこのへんで。