結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2020-10-11 01:47:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,399 ms / 5,000 ms |
コード長 | 1,274 bytes |
コンパイル時間 | 160 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 271,044 KB |
最終ジャッジ日時 | 2024-07-01 09:58:31 |
合計ジャッジ時間 | 13,465 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque def popcount(x): '''xの立っているビット数をカウントする関数 (xは64bit整数)''' # 2bitごとの組に分け、立っているビット数を2bitで表現する x = x - ((x >> 1) & 0x5555555555555555) # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333) x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと x = x + (x >> 8) # 16bitごと x = x + (x >> 16) # 32bitごと x = x + (x >> 32) # 64bitごと = 全部の合計 return x & 0x0000007f n = int(input()) steps = [None, 1] visited = [None, False] for _ in range(2, n+1): steps.append(-1) visited.append(False) q = deque([]) start = 1 q.append(start) while q: v = q.popleft() visited[v] = True if v == n: # print("goal") break num = popcount(v) for next_v in [v + num, v - num]: if 1 <= next_v and next_v <= n: if visited[next_v] == False: q.append(next_v) if steps[next_v] == -1: steps[next_v] = steps[v] + 1 else: steps[next_v] = min(steps[next_v], steps[v] + 1) print(steps[n])