結果

問題 No.3375 Binary Grid
コンテスト
ユーザー tassei903
提出日時 2025-11-21 22:54:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,985 ms / 2,000 ms
コード長 1,606 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 82,828 KB
最終ジャッジ日時 2025-11-21 22:54:19
合計ジャッジ時間 9,184 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

# m = 8
# for n in range(0, 1 << m):
#     s = []
#     for j in range(m):
#         if n >> j & 1:
#             s.append("O")
#         else:
#             s.append(" ")
#     print("".join(s), n)

"""
C が R の最上位 bitじゃない R を増やして 最上位bitに移動する

最上位に隣接していればいい
"""

def solve(r, c):
    k = len(bin(r)) - 2
    
    for i in range(c+1, k):
        if r >> i & 1 == 0:
            x = 0
            for j in range(i+1, k):
                if r >> j & 1:
                    x += 1 << j
            toR = 1 << i | x
            
            return solve(toR, i) + max(toR-r, i - c)
    
    return r - 1

m = 10
from collections import deque
def naive(r, c):
    dist = [[-1] * m for i in range(1 << m)]
    dist[1][0] = 0
    q = deque([(1, 0)])
    while q:
        x, y = q.popleft()
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < (1 << m) and 0 <= ny < m and dist[nx][ny] == -1 and nx >> ny & 1:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
    return dist[r][c]

m = 62
for _ in range(ni()):
    r, c = na()
    print(solve(r, c-1))
0