ARC115 C - ℕ Coloring

atcoder.jp

解説に反して、愚直みある実装でも解けた。

以下では1-indexedの方が理解しやすいと思ったので、あやしい+1と、出力時に0番目の無視をしている。
また、値はA1は必ず1、A2以降は必ず2以上、が明らかなので、答えの配列の初期値を1,2,2,...とすることで、最も計算回数の多い、i=1のパターンを無視した。

それ以降は、i=2,3,...それぞれにて、2なら4,6,... 、3なら6,9,...と、倍数に該当するものの値を、Aiの値と被らない＝現在値+1して、ただただ更新し続ける。
倍数が存在しえなくなるので、半分チョイまでのループとした。（深く考えてないが、切り上げならええやろ、、、程度。）

def resolve():
  N=int(input())+1
  
  ans=[2]*N
  ans[1]-=1
  
  for i in range(2,math.ceil(N/2)):
    val=ans[i]+1
    for j in range(2*i,N,i):
      ans[j]=val
 
  for i in range(1,N):
    print(ans[i],end=" ")

追記。

計算量危ないと思い込んで、↑ではアレコレやってみたものの、一切の高速化を廃しても、所要時間変わらず。
こういうのの計算量の見積もりがまだまだヘタだ…

def resolve():
  N=int(input())+1
  
  ans=[0]*N
  
  for i in range(1,N):
    val=ans[i]+1
    for j in range(i,N,i):
      ans[j]=val

  for i in range(1,N):
    print(ans[i],end=" ")