[白俊]繰り返し数列2331回

https://www.acmicpc.net/problem/2331
この問題を見ると,dfsを用いて繰返し値を得ると,dfsから抜け出して以前の数を得ることができると考えられる.
リストで実現し,ハッシュで実現したが,dfsを用いなくても実現できる方法がある.

私の最初の答え

アレイの範囲を設定します.9^5+9^5+9^5+9^5+9^5+9^5=約250000個のプリセット.D[i]=nの形で配列の対応するインデックスの値を変更するには、配列の範囲をあらかじめ決めておく必要があります.

繰り返し文を回して、次のD[i+1]の値を求めます.この値がD配列にある場合はbreak、ない場合はD[i+1]=valueで置き換えます.

D配列にnum値がある場合、その値から値が繰り返されるため、値のインデックスが見つかり、-1の値が正しい.(-1の理由は、D[1]から値の提供を開始したためである.)

import sys A, P = map(int,sys.stdin.readline().split()) D = [0]*250000 D[1] = A index = 1 while True: num = 0 index += 1 for n in str(D[index-1]): num += (int(n)**P) if num in D: print(D.index(num) - 1) break else: D[index] = num

上記のような方法で解くこともできます.

import sys A, P = map(int,sys.stdin.readline().split()) def repeat(n): num_list = [n] while(True): temp = 0 for i in str(num_list[len(num_list)-1]): temp += int(i)**P if temp in num_list: break else: num_list.append(temp) return num_list.index(temp) print(repeat(A))

私の2番目の答え

dfsを使って問題を解くのも見ました.

D配列では,同様に250000個を初期化した.

再帰関数を実現し、D[57]=1、D[74]=2、D[65]=3のようにD[A]=cnt++として現れる.

脱出式はD[A]!=0の場合、すなわち、かつてアクセスしたインデックスが表示された場合、そのcnt値に-1を加算し、dfs()を終了します.

D[A]=1を設定したのは、重複数列が最初の値から始まると正解が0になるからです.

import sys sys.setrecursionlimit(10000) A, P = map(int,sys.stdin.readline().split()) D = [0]*250000 D[A] = 1 def dfs(A, cnt): num = 0 for n in str(A): num += (int(n)**P) if D[num] != 0: print(D[num]-1) return else: cnt += 1 D[num] = cnt dfs(num, cnt) dfs(A, D[A])