結果

問題 No.3 ビットすごろく
コンテスト
ユーザー nbisco
提出日時 2016-04-09 22:15:42
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,088 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 97 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 53,888 KB
最終ジャッジ日時 2024-10-04 05:09:13
合計ジャッジ時間 7,072 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env python3
#fileencoding: utf-8

def popcnt(i):
    count = 0
    while i > 0:
        count += (i&0x1)
        i >>= 1
    return count

def solver(mat, hist, N):
    if hist[-1] == 0:
        return len(hist)+1
    route = N
    for i in range(N-1):
        if mat[hist[-1]][i] == 0:
            continue
        if i not in hist:
            tmp = solver(mat, hist+[i], N)
            if route > tmp:
                route = tmp
    return route

def main():
    N = int(input().strip())
    if N == 1:
        return 1

    mat = [[0]*N for i in range(N)]
    for i in range(N):
        bits = popcnt(i+1)
        if (i - bits) >= 0:
            mat[i-bits][i] = 1
        if (i + bits) < N:
            mat[i+bits][i] = 1

    if sum(mat[N-1]) == 0: # ゴールできない
        return -1

    goal = mat[N-1]
    route = N
    for i in range(N-1):
        if goal[i] == 0:
            continue
        route_temp = solver(mat, [i], N)
        if route_temp < route:
            route = route_temp
    if route == N:
        route = -1
    return route

print(main())
0