結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2020-07-14 17:10:32 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 64 ms / 5,000 ms |
コード長 | 1,016 bytes |
コンパイル時間 | 85 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-07-01 09:52:46 |
合計ジャッジ時間 | 2,657 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import queue N=int(input()) def calcpop(num): return bin(num).count("1") def bit(): q=queue.Queue() q.put(1) trout=[-1]*(10**5) trout[1]=1 while q.empty()==False: curpos=q.get() #現在のマス目 popcnt=calcpop(curpos) #現在のマス目を2進数に変換した時の1の数 if(trout[curpos-popcnt]==-1 and curpos-popcnt>0): #後ろのマスに移動するときの判定・処理 trout[curpos-popcnt]=trout[curpos]+1 #移動した先に移動数の最小値を記録 q.put(curpos-popcnt) #このマス目から次は探索を行うためキューに入れる if(trout[curpos+popcnt]==-1 and curpos+popcnt<=N): #前のマスに移動する時の判定・処理 trout[curpos+popcnt] = trout[curpos] + 1 #移動した先に移動数の最小値を記録 q.put(curpos+popcnt) #このマス目から次は探索を行うためキューに入れる print(trout[N]) if __name__ == "__main__": bit()