AtCoder Beginner Contest 170を見直す(その3）

前回分

今回は解けなかったD問題に（解説動画見て）挑戦しました！

D - Not Divisible

D - Not Divisible

問題

整数列が与えられるので、その中で整数列に含まれる他の整数で割り切れない数字の数を求めなさい。

制約

数列の長さは2*10^5
整数の最大値は10^6

例

入力：24 11 8 3 16
上記の場合、24は8,3で割り切れ、16も8で割り切れる。他の３つの数字は割り切れる他の数字がないので答えは3となる。

解説のままに作成した解答

N = int(input())
A_list = list(map(int, input().split()))
M = max(A_list) + 1
cnt = [0 for _ in range(M)]

for i in A_list:
   if cnt[i] != 0:
       cnt[i] = 2
       continue
   for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
   if cnt[k] == 1: ans += 1
print(ans)

うん。結構シンプル。ちなみに私が当日に作成して正解できなかったコードはこれの３倍ぐらい長い上に、計算量も以上に多いです。

理解を深めるために解説

割り切れる数がないかを一つ一つの数に対して確認すると、全部素数だった場合最大「4*10^10」回計算することになり、時間超過になってしまいます。発想を逆転させて一つ一つの数の倍数を記録して倍数の数が一つ、つまり自分だけの場合を数え上げれば良いです。わかりづらいので処理の流れで見てみることにします。

入力：2 4 8 5 3
① まず、入力値に応じて９個の「0」で構成されたリストを作成します
cnt = [0,0,0,0,0,0,0,0,0]
② 2の倍数をカウントアップします
cnt = [0,0,1,0,1,0,1,0,1]
③ 4の倍数をカウントアップします
cnt = [0,0,1,0,2,0,1,0,2]
④ 8の倍数をカウントアップします
cnt = [0,0,1,0,2,0,1,0,3]
⑤ 5の倍数をカウントアップします
cnt = [0,0,1,0,2,1,1,0,3]
⑥ 3の倍数をカウントアップします
cnt = [0,0,1,1,2,1,2,0,3]
⑦各々の数について倍数の数を確認し、「1」であれば自分を割り切れる数字は自分だけです。
cnt[2] >> 1
cnt[4] >> 2
cnt[8] >> 3
cnt[5] >> 1
cnt[3] >> 1
⑧よって「1」が3つあったので、出力は3となります。

この算出方法に一つ懸念があるとすれば、最大値である「10^6」と「1」が複数個含まれる場合、そのまま計算すると「1の数*10^6」回ループが回ってしまうことです。それだとやはり時間超過になってしまうので、「既に倍数が記録されている場合は、倍数が2であることを記録し、倍数のカウントは行わない処理」を入れています。

うーん、面白い。