結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2017-11-29 10:46:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,072 bytes |
コンパイル時間 | 180 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 23,296 KB |
最終ジャッジ日時 | 2024-11-27 18:51:27 |
合計ジャッジ時間 | 84,488 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 TLE * 9 |
ソースコード
import sys sys.setrecursionlimit(10000) N=int(input()) #Nのビット数 n_bit=0 tmp=N while(tmp!=0): n_bit+=1 tmp=int(tmp/2) # print(n_bit) #'1'をカウント one_num_list=[0 for i in range(N+1)] for i in range(N+1): mask=0b1 one_sum=0 for l in range(n_bit): if i&mask!=0: one_sum+=1 mask=mask<<1 one_num_list[i]=one_sum #kに到達できる最小の移動数を順に調べていく(ただし-1のとき移動できないとする) move_num=[-1 for i in range(N+1)] #境界条件 move_num[0]=0 move_num[1]=1 #全探索 def Update(k): # print(k) if move_num[k]==-1: return one_num=one_num_list[k] #前の更新 if move_num[k-one_num]==-1 or move_num[k-one_num]>move_num[k]+1: move_num[k-one_num]=move_num[k]+1 Update(k-one_num) #後ろの更新 if k+one_num>N: return if move_num[k+one_num]>move_num[k]+1 or move_num[k+one_num]==-1: move_num[k+one_num]=move_num[k]+1 Update(k+one_num) Update(1) # print(move_num) print(move_num[N])