#993582 (PyPy3) No.3 ビットすごろく

提出ソース

結果

問題	No.3 ビットすごろく
ユーザー	Arleen
提出日時	2024-07-11 01:31:17
言語	PyPy3 (7.3.15)
結果	AC
実行時間	117 ms / 5,000 ms
コード長	11,974 bytes
コンパイル時間	1,065 ms
コンパイル使用メモリ	82,048 KB
実行使用メモリ	80,000 KB
最終ジャッジ日時	2024-07-11 01:31:23
合計ジャッジ時間	5,859 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	56 ms 64,384 KB
testcase_01	AC	57 ms 64,000 KB
testcase_02	AC	55 ms 64,384 KB
testcase_03	AC	89 ms 78,680 KB
testcase_04	AC	71 ms 69,248 KB
testcase_05	AC	88 ms 78,788 KB
testcase_06	AC	87 ms 78,720 KB
testcase_07	AC	79 ms 75,520 KB
testcase_08	AC	109 ms 79,336 KB
testcase_09	AC	94 ms 78,372 KB
testcase_10	AC	90 ms 78,976 KB
testcase_11	AC	88 ms 78,412 KB
testcase_12	AC	89 ms 78,688 KB
testcase_13	AC	86 ms 78,436 KB
testcase_14	AC	91 ms 79,172 KB
testcase_15	AC	92 ms 79,464 KB
testcase_16	AC	92 ms 79,348 KB
testcase_17	AC	92 ms 79,744 KB
testcase_18	AC	86 ms 78,588 KB
testcase_19	AC	117 ms 80,000 KB
testcase_20	AC	60 ms 66,816 KB
testcase_21	AC	56 ms 64,384 KB
testcase_22	AC	90 ms 78,828 KB
testcase_23	AC	96 ms 79,984 KB
testcase_24	AC	94 ms 79,848 KB
testcase_25	AC	93 ms 79,532 KB
testcase_26	AC	57 ms 64,012 KB
testcase_27	AC	86 ms 78,800 KB
testcase_28	AC	91 ms 79,360 KB
testcase_29	AC	88 ms 78,380 KB
testcase_30	AC	57 ms 64,896 KB
testcase_31	AC	56 ms 65,152 KB
testcase_32	AC	94 ms 78,752 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
import itertools
import time
import heapq
from math import radians, sin, cos, tan, sqrt, comb, pow
from math import log, log2, log10, exp
from collections import deque
from operator import mul
from functools import reduce, cmp_to_key
from random import randint, randrange
from bisect import bisect_left, bisect_right

def input():
    return sys.stdin.readline().replace('\n','')
#sys.setrecursionlimit(300000)
md1 = 998244353
md2 = 10 ** 9 + 7
inf = 2 ** 31 + 1
primeset = set()
primelist = []
fenwick = []

# 入力ツール
# 1行の入力を整数のリストとして受け取る
def intlist():
    return list(map(int, input().split()))

# 1行から複数個の整数を受け取る
def getints():
    return tuple(map(int, input().split()))

# n行の入力を文字列のリストとして受け取る
def strtable(n):
    lst = []
    for i in range(0, n):
        lst.append(input())
    return lst

# n行の入力を整数のリストとして受け取る
def inttable(n):
    return list(map(int, strtable(n)))

# 整数のリストをn個受け取る
def intlisttable(n):
    lst = []
    for i in range(0, n):
        lst.append(intlist())
    return lst

# n個のクエリを先頭だけ整数、他を文字列のリストとして受け取る
def getquery(n):
    lst = []
    for i in range(0, n):
        query = list(input().split())
        qr = int(query[0])
        lst.append((qr, query[1:]))
    return lst

#==========
# 生成ツール
# H行W列のリスト生成
def twodimlist(h, w, init): # initの値で初期化
    lst1 = []
    for i in range(0, h):
        lst2 = []
        for j in range(0, w):
            lst2.append(init)
        lst1.append(lst2)
    return lst1

# 素数テーブルをsetとして生成
def genprimeset(n): #n以下の素数を列挙
    global primeset, primelist
    left = list(primeset)
    right = deque()
    start = 2
    if len(left) != 0:
        start = pt[-1] + 1
    for i in range(start, n+1):
        right.append(i)
    while len(right) != 0:
        flag = True
        now = right.popleft()
        for i in range(0, len(left)):
            if now < left[i] ** 2:
                break
            if now % left[i] == 0:
                flag = False
                break
        if flag:
            left.append(now)
    return set(left)

#==========
# 数え上げ
# 1次元数え上げ
def cntx(itr, x):
    cnt = 0
    for i in range(0, len(itr)):
        if itr[i] == x:
            cnt += 1
    return cnt

# 2次元数え上げ
def twodimcntx(itr, x):
    sm = 0
    for i in range(0, len(itr)):
        sm += cntx(itr[i], x)
    return sm

# 全要素数え上げ
def allcnt(itr):
    dct = {}
    for i in range(0, len(itr)):
        if itr[i] not in dct:
            dct[itr[i]] = 0
        dct[itr[i]] += 1
    return dct

# 2次元全要素数え上げ
def twodimallcnt(itr, x):
    dct = {}
    for i in range(0, len(itr)):
        for j in range(0, len(itr[i])):
            if itr[i][j] not in dct:
                dct[itr[i][j]] = 0
            dct[itr[i][j]] += 1
    return dct

#==========
# 計算ツール
# 最大公約数
def gcd(x, y):
    if x < y:
        return gcd(y, x)
    if x % y == 0:
        return y
    return gcd(y, x%y)

# 最小公倍数
def lcm(x, y):
    g = gcd(x, y)
    return (x*y) // g

# フィボナッチ数列(0-indexで、第n項まで生成)
def genfib(n, m): # m == 0ならmodなし、m == 1ならmd1でmod, m == 2ならmd2でmod
    lst = [1, 1]
    if m == 0:
        for i in range(1, n):
            lst.append(lst[-2]+lst[-1])
    else:
        md = md1
        if m == 2:
            md = md2
        for i in range(1, n):
            lst.append((lst[-2]+lst[-1])%md)
    return lst

# 素数一覧の初期化
def primeinit(x):
    global primeset, primelist
    primeset = genprimeset(x)
    primelist = list(primeset)
    return

# 素数判定
def isitprime(x):
    if x < 2:
        return False
    global primeset, primelist
    if len(primeset) == 0:
        primeinit(int(sqrt(x))+10)
    elif primelist[-1] ** 2 < x:
        primeinit(int(sqrt(x))+10)
    if x in primeset:
        return True
    for i in range(0, len(primelist)):
        if x % primelist[i] == 0:
            return False
    return True

# 素因数分解
def factorize(x):
    global primeset, primelist
    if len(primeset) == 0:
        primeinit(int(sqrt(x))+10)
    elif primelist[-1] ** 2 < x:
        primeinit(int(sqrt(x))+10)
    dct = {}
    now = x
    for i in range(0, len(primelist)):
        if x < primelist[i] ** 2:
            break
        while now % primelist[i] == 0:
            if primelist[i] not in dct:
                dct[primelist[i]] = 0
            dct[primelist[i]] += 1
            now //= primelist[i]
    if now != 1:
        dct[now] = 1
    return dct

# Coprime判定
def coprime(x, y):
    return gcd(x, y) == 1

# 約数列挙
def divisor(x):
    s = set()
    for i in range(1, x+1):
        if x < i ** 2:
            break
        if x % i == 0:
            s.add(i)
            s.add(x//i)
    lst = sorted(list(s))
    return lst

# 約数数え上げ
def countdivisor(x):
    fact = factorize(x)
    key = list(fact.keys())
    cnt = 1
    for i in range(0, len(key)):
        cnt *= fact[key[i]] + 1
    return cnt

# 大文字->小文字変換
def uppertolower(c):
    if 'A' <= c and c <= 'Z':
        return chr(ord(c)+32)
    return c

# 小文字->大文字変換
def lowertoupper(c):
    if 'a' <= c and c <= 'z':
        return chr(ord(c)-32)
    return c

# 大文字小文字相互変換
def upperlower(c):
    newc = uppertolower(c)
    if c == newc:
        newc = lowertoupper(c)
    return newc

# x以上の要素の個数
def xormore(lst, x): # lstはソート済みにすること
    return len(lst) - bisect_left(lst, x)

# xより大きい要素の個数
def morethanx(lst, x): # lstはソート済みにすること
    return len(lst) - bisect_right(lst, x)

# x以下の要素の個数
def xorless(lst, x): # lstはソート済みにすること
    return bisect_right(lst, x)

# x未満の要素の個数
def lessthanx(lst, x): # lstはソート済みにすること
    return bisect_left(lst, x)

# 各桁の総和
def digitsum(x):
    nm = str(x)
    sm = 0
    for i in range(0, len(nm)):
        sm += int(nm[i])
    return sm

# bitカウント(64bitまで)
def popcount(x):
    now = x
    now = now - ((now >> 1) & 0x5555555555555555)
    now = (now & 0x3333333333333333) + ((now >> 2) & 0x3333333333333333)
    now = (now + (now >> 4)) & 0x0f0f0f0f0f0f0f0f
    n = 8
    for i in range(0, 3):
        now += (now >> n)
        n *= 2
    return now & 0x0000007f

# xの累乗リスト(0乗からn乗まで)
def powtable(x, n, m): # modなしの場合はm = 0に設定する
    md = m
    if m == 1: # m == 1ならmd1でmod
        md = md1
    elif m == 2: # m == 2ならmd2でmod
        md = md2
    
    lst = [1]
    for i in range(0, n):
        if md == 0:
            lst.append(lst[-1]*x)
        else:
            lst.append((lst[-1]*x)%md)
    return lst

# ==========
# グラフツール
# グラフの初期化
def defgraph(vlist):
    graph = {}
    for i in range(0, len(vlist)):
        graph[vlist[i]] = set()
    return graph

# 重み付きグラフの初期化
def defgraphw(vlist):
    graph = {}
    for i in range(0, len(vlist)):
        graph[vlist[i]] = {}
    return graph

# 無向グラフ生成
def undirgraph(vlist, elist): # 辺の形式は(u, v)
    graph = defgraph(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u].add(v)
        graph[v].add(u)
    return graph

# 重み付き無向グラフ生成
def undirgraphw(vlist, elist, wdict):
    graph = defgraphw(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u][v] = wdict[elist[i]]
        graph[v][u] = wdict[elist[i]]
    return graph

# 有向グラフ生成
def dirgraph(vlist, elist): # 辺の形式は(u, v)で、向きはu -> v
    graph = defgraph(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u].add(v)
    return graph

# 重み付き有向グラフ生成
def dirgraphw(vlist, elist, wdict):
    graph = defgraphw(vlist)
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        graph[u][v] = wdict[elist[i]]
    return graph

# 重み無し最短ステップ
def shortest(vlist, elist, graph, st, gl):
    if st not in graph or gl not in graph:
        return -1
    yet = set(vlist)
    q = deque()
    q.append((st, 0))
    yet.discard(st)
    while len(q) != 0:
        now = q.popleft()
        v = now[0]
        s = now[1]
        if v == gl:
            return s
        lst = list(graph[v])
        for i in range(0, len(lst)):
            nxtv = lst[i]
            if nxtv in yet:
                yet.discard(nxtv)
                q.append((nxtv, s+1))
    return -1

# Dijkstra(WIP)
def dijkstra(vlist, elist, graph):
    #WIP
    return

# Union-Find生成
def genunionfind(vlist, elist): # 辺の形式は(u, v)
    graph = defgraph(vlist)
    root = {}
    vcnt = {}
    flag = False
    for i in range(0, len(vlist)):
        root[vlist[i]] = vlist[i]
        vcnt[vlist[i]] = 1
    for i in range(0, len(elist)):
        u = elist[i][0]
        v = elist[i][1]
        ur = root[u]
        vr = root[v]
        if ur == vr:
            flag = True
        else:
            H = ur
            L = vr
            if vcnt[ur] < vcnt[vr]:
                H = vr
                L = ur
            graph[H].add(L)
            vcnt[H] += vcnt[L]
            q = deque()
            q.append(L)
            while len(q) != 0:
                now = q.popleft()
                root[now] = H
                lst = list(graph[now])
                for j in range(0, len(lst)):
                    q.append(lst[j])
    return (graph, root, vcnt, flag) # (グラフ, 根, 頂点の数, ループ検出)の形式で返す

# ==========
# fenwick木
# fenwickを初期化
def initfenwick(n, init):
    global fenwick
    fenwick = []
    for i in range(0, n+1):
        fenwick.append(init)
    return

# idx番目までの和を求める
def fwsum(idx):
    sm = 0
    now = idx
    while now > 0:
        sm += fenwick[now]
        now -= -now & now
    return sm

# idx番目の値にxを足す
def fwadd(idx, x):
    global fenwick
    now = idx
    while now < len(fenwick):
        fenwick[now] += x
        now += -now & now
    return

# 転倒数
def inversion(A):
    global fenwick
    initfenwick(len(A), 0)
    sm = 0
    for i in range(0, len(A)):
        sm += i - fwsum(A[i])
        fwadd(A[i], 1)
    return sm

# ==========
# ハッシュ(WIP)
Mset = set()
Mlist = []
def initM():
    global Mset
    global Mlist
    a = 10 ** 9
    for i in range(-10000, 10001):
        if isitprime(a+i):
            Mset.add(a+i)
    Mlist = list(Mset)
    return

# ==========
# 【問題要約】
# 1からNまでの番号が振られたN個のマスが一直線上に並んだすごろくがある
# 振り出しは1のマス、あがりはNのマスである
# マスi(where 1<=i<=N)にいるときは、iを2進数表記した時の1の個数分だけ前か後ろに進める
# 1未満やN+1以上のマスに移動することはできない
# また、ちょうどNに止まった場合のみあがり扱いになる
# 正整数Nが与えられるので、ゴールに到達するために必要な移動数の最小値を求めよ
#
# ==========
# コードはここから書く
N = int(input())
vlist = list(range(1, N+1))
elist = []
for i in range(1, N+1):
    bcnt = popcount(i)
    bck = i - bcnt
    frw = i + bcnt
    if 1 <= bck:
        elist.append((i, bck))
    if frw <= N:
        elist.append((i, frw))

graph = dirgraph(vlist, elist)
step = shortest(vlist, elist, graph, 1, N)
ans = -1
if step != -1:
    ans = step + 1
print(ans)

yukicoder

結果

テストケース

ソースコード