結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2020-09-05 18:19:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 57 ms / 5,000 ms |
コード長 | 636 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 65,920 KB |
最終ジャッジ日時 | 2024-07-01 09:54:46 |
合計ジャッジ時間 | 2,902 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque def popcount(x): x -= (x >> 1) & 0x5555 x = (x & 0x3333) + ((x >> 2) & 0x3333) x = (x + (x >> 4)) & 0x0f0f x += x >> 8 return x & 0x1f N = int(input()) X = [[] for i in range(N + 1)] for i in range(1, N): pc = popcount(i) if i - pc > 0: X[i].append(i - pc) if i + pc <= N: X[i].append(i + pc) def BFS(n, E, i0=0): Q = deque([i0]) D = [-1] * n D[i0] = 1 while Q: x = Q.popleft() for c in E[x]: if D[c] == -1: D[c] = D[x] + 1 Q.append(c) return D print(BFS(N + 1, X, 1)[-1])