結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2025-03-30 18:33:01 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 68 ms / 5,000 ms |
コード長 | 787 bytes |
コンパイル時間 | 282 ms |
コンパイル使用メモリ | 12,160 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2025-03-30 18:33:05 |
合計ジャッジ時間 | 3,130 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque def popcount(x): return bin(x).count('1') def shortest_moves(N): # 最短移動数を格納するDPテーブル(未訪問は-1) dp = [-1] * (N + 1) dp[1] = 1 # 開始のマスも移動にカウントする queue = deque([1]) while queue: current = queue.popleft() step = popcount(current) # 次の候補マス for next_pos in [current - step, current + step]: if 1 <= next_pos <= N and dp[next_pos] == -1: dp[next_pos] = dp[current] + 1 queue.append(next_pos) # print(current, next_pos, queue, list(queue), dp) return dp[N] # 入力受付と実行 if __name__ == "__main__": N = int(input()) print(shortest_moves(N))