結果

問題 No.3 ビットすごろく
コンテスト
ユーザー G
提出日時 2026-04-15 11:17:13
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 105 ms / 5,000 ms
コード長 817 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 343 ms
コンパイル使用メモリ 20,824 KB
実行使用メモリ 15,488 KB
最終ジャッジ日時 2026-04-15 11:17:25
合計ジャッジ時間 4,873 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

N = int(input())

# N=1 の場合はスタートがそのままゴール
if N == 1:
    print(1)
    exit()

# 訪問済み管理
visited = [False] * (N + 1)

# キュー: (現在位置, 移動回数)
queue = deque()
queue.append((1, 1))  # スタート地点も回数に含める
visited[1] = True

while queue:
    pos, count = queue.popleft()

    # ゴールに到達した場合
    if pos == N:
        print(count)
        break

    # 現在位置の1のビット数
    step = bin(pos).count("1")

    # 前後に移動
    for next_pos in (pos + step, pos - step):
        if 1 <= next_pos <= N and not visited[next_pos]:
            visited[next_pos] = True
            queue.append((next_pos, count + 1))
else:
    # ゴールに到達できなかった場合
    print(-1)
0