結果

問題 No.3 ビットすごろく
ユーザー Mottchan
提出日時 2025-02-01 16:38:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 152 ms / 5,000 ms
コード長 6,185 bytes
コンパイル時間 559 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 78,104 KB
最終ジャッジ日時 2025-02-01 16:38:20
合計ジャッジ時間 5,707 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.set_int_max_str_digits(0)
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right

## gcd(x, y):最大公約数, lcm(x, y):最小公倍数, factorial(n):階乗n!, prem(n, k):nPk(n, k), comb(n, r):二項係数nCr
from math import gcd, lcm, factorial, perm, comb 

#0~9を並び替えるならpermutationsかconbinations,N列のカテゴリを作るにはproduct
from itertools import product, permutations, combinations, accumulate

from functools import lru_cache #@lru_cache(maxsize=128)
import operator
from string import ascii_uppercase, ascii_lowercase, digits # 英字(大文字), 英字(小文字), 数字

MOD = 998244353

def II():return int(input())
def LI():return list(input())
def LMI():return list(map(int, input().split()))
def LMS():return list(map(str, input().split()))
def LLMI(x):return [list(map(int, input().split())) for _ in range(x)]
def LLMS(x):return [list(input()) for _ in range(x)]

def CUM(x:list) -> list:
    '''
        func:累積の仕方を指定する。
            operator.mul:掛け算
            operator.sub:引き算
            max:最大値
            min:最小値
        initial:初期値, Noneならx[0]が第一引数の数値になる
    '''
    return list(accumulate(x, func=None, initial=0))

def yn(tf:bool):
    if tf:
        return print('YES')
    else:
        return print('No')

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def group(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return ''.join(f'{r}: {m}' for r, m in self.group().items())


def inverse_element(num:int):
    '''
        逆元の作成
        ax ≡ 1 (mod p)となるxは、fetmatの小定理より
        a * a^(p-2) ≡ 1 (mod p)であるため、
        a^(p-2) (mod p) は逆元である
    '''
    return pow(num, MOD-2, MOD)

def make_graph(n:int, lmi:list, idx_0:bool = True, is_direct:bool = False):
    graph = [[] for _ in range(n)]
    for i in range(len(lmi)):
        a, b = lmi[i]
        if idx_0:
            a -= 1
            b -= 1
        # 有向グラフであれば1方向にappendする。
        graph[a].append(b)
        if not is_direct:
            graph[b].append(a)
    
    return graph

def bfs(n:int,  graph:list[list[int]], s:int = 0, g:int = None):
    '''
        s:start地点、指定しなければ頂点0から
        g:goal地点、指定しなければ端まで
    '''
    d = deque([(s, 0)])
    TF = [False] * n
    while d:
        crr, cnt = d.popleft()
        TF[crr] = True

        for nxt in graph[crr]:
            if nxt == g:
                return cnt+1
            if TF[nxt]:continue
            d.append((nxt, cnt+1))
            TF[nxt] = True
    
    return -1

def dfs(n:int,  graph:list[list[int]], s:int = 0, g:int = None):
    '''
        s:start地点、指定しなければ頂点0から
        g:goal地点、指定しなければ端まで
    '''
    d = deque([(s, 0)])
    TF = [False] * n
    while d:
        crr, cnt = d.pop()
        TF[crr] = True
        
        for nxt in graph[crr]:
            if TF[nxt]:continue
            d.append((nxt, cnt+1))
            TF[nxt] = True

def dijkstra(n:int,  graph:list[list[int, int]], s:int = 0):
    '''
        s:start地点、指定しなければ頂点0から
    '''

    que = []
    heappush(que, (0, s))
    TF = [False] * n
    # 各頂点の最短経路を格納する
    ans = [0] * n

    while que:
        cnt, crr = heappop(que)
        if TF[crr]: continue
        # 最短経路確定
        TF[crr] = True
        ans[crr] = cnt

        for nxt, val in graph[crr]:
            # 最短経路が確定しているところは除く
            if TF[nxt]:continue
            heappush(que, (cnt+val, nxt))
    else:
        return ans

def make_adjacency_matrix(n:int, nodes:list):
    matrix = [[float('INF')]*n for _ in range(n)]
    for node in nodes:
        v, m, c = node
        matrix[v][m] = c
        matrix[m][v] = c
    for i in range(n):
        matrix[i][i] = 0

    return matrix

def Floyd_Warchall_Algorithm(n, matrix):
    '''
    n:
        [int]頂点の数
    matrix:
        [list]隣接行列
    '''
    for k in range(n):
        for i in range(n):
            for j in range(n):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

    return matrix

def ont_bit_cnt(n):
    cnt = 0
    for i in range(40):
        if (n >> i) & 1 == 1:
            cnt += 1
    return cnt


def execute():
    n = II()
    dp = [-1] * n
    dp[0] = 0
    d = deque()
    d.append(0)
    while d:
        num = d.popleft()
        cnt = ont_bit_cnt(num+1)
        if num+cnt < n:
            if dp[num+cnt] == -1:
                dp[num+cnt] = dp[num] + 1
                d.append(num+cnt)
        if num-cnt >= 0:
            if dp[num-cnt] == -1:
                dp[num-cnt] = dp[num] + 1
                d.append(num-cnt)
        # print(dp)

    if dp[n-1] == -1:
        print(-1)
    else:
        print(dp[n-1]+1)

if __name__ == "__main__":
    T = 1
    for _ in range(T):
        execute()
0