結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2020-11-27 19:29:04 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
RE
|
実行時間 | - |
コード長 | 874 bytes |
コンパイル時間 | 97 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 44,820 KB |
最終ジャッジ日時 | 2024-07-23 21:42:37 |
合計ジャッジ時間 | 19,141 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | RE * 33 |
ソースコード
# 深さ優先探索で解きましたimport numpy as npdef dfs(g, v, prev_v):previous_vs[v] = prev_vseen[v] = Truenext_vs = g[v]for next_v in next_vs:if seen[next_v]:continuedfs(g, next_v, v)N = int(input())lengths = [bin(i).count('1') for i in range(1,N+1)]g = []for i, length in enumerate(lengths):edges = []forward = i+lengthbackward = i-lengthif not backward < 0:edges.append(backward)if not forward > N-1:edges.append(forward)g.append(edges)seen = np.zeros_like(lengths, np.bool)previous_vs = np.full_like(lengths, -1)dfs(g, 0, -1)if seen[N-1]:count = 1previous_v = N-1while True:previous_v = previous_vs[previous_v]count = count + 1if previous_v == 0:breakprint(count)else:print(-1)