初めに
本記事はPythonでAtcoderにチャレンジしているけど、Pythonはコード例がないため解説がわかりにくい！と感じている方を対象としています。
私自身大してレートも高くないので、不備等あるかもしれませんがご了承くださいm(_ _)m
質問や指摘などもコメント等に書いてくださったら対応していきたいと考えていますのでどしどしコメントしてください。(内容がわかりにくいぞ！みたいな文句でもオールオッケーです笑)
Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）
問題のURLはこちらです。Toyota Programming Contest 2023 Spring Qual B C問題
考え方
問題文の条件として、「順序を変えずに抜き取る」という文言が書かれていますが、これは無視して構いません。なぜなら、MEXの出力に、入力した数列の順序は影響を及ぼさないからです。
例として、$B=[0,2,1],B=[2,0,1]$という数列を考えてみると、
どちらも$MEX=3$となることがわかります。
今回重要なポイントは、与えられた数列Aを調べていき、「0,1,2,・・・・・」と値が入っているのかどうかが重要です。
従って、今問題の解法としては数列Aをソートし、0から順番に値が格納されているのか調べることで、解を求めることができます。
実装例
#標準入力
n,k = map(int,input().split())
a = list(map(int,input().split()))
#aをソートした配列を作成
re_a = sorted(a)
#mexの初期値を設定
num = 0
for i in re_a :
if num == i :
num += 1
if num >= k :
break
print(num)
最後に
私は最初、以下のようなコードを書きました。
n,k = map(int,input().split())
a = list(map(int,input().split()))
num = 0
count = 0
booler = True
while booler :
if num in a :
count += 1
num += 1
else :
booler = False
break
if count >= k :
break
print(num)
今コードはソートをかけずに、numを0から1ずつ増やしていって、配列aの中にその値が入っているのか調べるコードです。
これはTLEしたのですが、この原因は「if num in a」というコードが邪魔しているからです。
配列の中にある値が格納されているのか否かを調べる「in list」という処理は、ここだけで計算量が$O(N)$ かかります。
従って、今コードの計算量は$O(N^2)$となっているため、TLEしました。
これまであまり内部の処理に気を配っていなかったので、今後は気をつけたいです汗
ちなみに、その他処理にかかる計算量がこちらの記事にまとめられているので、ぜひぜひ読んでみてください。