[BOJ] 12851. かくれんぼをする

提问链接

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())

q = deque()

q.append((0, n))
ans = int(1e9)
ans_cnt = 0
dp = [int(1e9)] * 100001
while q:
  cnt, now = q.popleft()

  if now == k:
    if ans == int(1e9):
      ans = cnt
      ans_cnt += 1
    elif cnt == ans:
      ans_cnt += 1
    continue

  if cnt > ans:
    break

  else:
    if now - 1 >= 0 and cnt + 1 <= dp[now - 1]:
      q.append((cnt + 1, now - 1))
      dp[now - 1] = cnt + 1
    if now + 1 <= 100000 and cnt + 1 <= dp[now + 1]:
      q.append((cnt + 1, now + 1))
      dp[now + 1] = cnt + 1
    if now * 2 <= 100000 and cnt + 1 <= dp[now * 2]:
      q.append((cnt + 1, now * 2))
      dp[now * 2] = cnt + 1

print(ans)
print(ans_cnt)

BFSアルゴリズムを用いた問題
配列を使用して、対応するインデックス(場所)に時間を格納します.
時間が経つと、対応する値がリフレッシュされます.
そこで,まず配列値を10億にリセットする.
その後、まず秀彬が0秒のとき、nの位置にあるので、キューに(0,n)を入れます.
キュー内のpopの位置がkの場合、if文を再使用して問題を解きます.
最初はheapqで問題を解き始めたが、タイムアウトした.

## 12851. 숨바꼭질2

import sys
import heapq
input = sys.stdin.readline

n, k = map(int, input().split())

arr = []

heapq.heappush(arr, (0, n))
ans = int(1e9)
ans_cnt = 0
while arr:
  cnt, now = heapq.heappop(arr)
  # print(cnt, now)

  if now == k:
    if ans == int(1e9):
      ans = cnt
      ans_cnt += 1
    elif cnt == ans:
      ans_cnt += 1
    continue

  if cnt >= ans:
    break

  else:
    if now - 1 >= 0:
      heapq.heappush(arr, (cnt + 1, now - 1))
    if now + 1 <= 100000:
      heapq.heappush(arr, (cnt + 1, now + 1))
    if now * 2 <= 100000:
      heapq.heappush(arr, (cnt + 1, now * 2))

print(ans)
print(ans_cnt)

いずれにしても、配列があれば、配列インデックスで値に直接アクセスできるので、タイムアウトは発生しません.
21.004.07復習

## 12851. 숨바꼭질
import heapq
n, k = map(int, input().split())

INF = int(1e9)
dp = [INF for _ in range(100001)]

q = []

heapq.heappush(q, (0, n))
ans = INF
cnt = 0
while q:
  sec, now = heapq.heappop(q)
  
  if sec > ans:
    break
    
  if now == k:
    if ans == INF:
      ans = sec
      cnt += 1
    elif ans == sec:
      cnt += 1
    else:
      break

  
  if now - 1 >= 0 and dp[now - 1] >= sec + 1:
    dp[now - 1] = sec + 1
    heapq.heappush(q, (sec + 1, now - 1))
  if now + 1 <= 100000 and dp[now + 1] >= sec + 1:
    dp[now + 1] = sec + 1
    heapq.heappush(q, (sec + 1, now + 1))
  if now * 2 <= 100000 and dp[now * 2] >= sec + 1:
    dp[now * 2] = sec + 1
    heapq.heappush(q, (sec + 1, now * 2))

print(ans)
print(cnt)

今回はdpとheapqを使います.

  if now == k:
    if ans == INF:
      ans = sec
      cnt += 1
    elif ans == sec:
      cnt += 1
    else:
      break

最初はこの条件文を書き間違えて78%で失敗した.

  if now == k:
    if ans == INF:
      ans = dp[now] 
      cnt += 1
    elif dp[now] == sec:
      cnt += 1
    else:
      break

dp[now]とsecは常に同じ値である.
私はansを使うべきですが、dp[now]で書くので、
そして.

  if sec > ans:
    break

この条件がなくても成功する.

写真からわかるように、時間を大幅に短縮できます!
21.06.29復習

import sys  
import heapq

input = sys.stdin.readline

n, k = map(int, input().split())
q = []
heapq.heappush(q, (0, n))
INF = int(1e9)
dp = [INF for _ in range(100001)]
min_cnt = INF
answer_cnt = 0

while q: 
  cnt, n = heapq.heappop(q)

  if n == k:
    if min_cnt == INF:
      min_cnt = cnt
      answer_cnt = 1
    elif cnt == min_cnt:
      answer_cnt += 1
    else:
      break

  if n - 1 >= 0 and dp[n - 1] >= cnt + 1:
    dp[n - 1] = cnt + 1
    heapq.heappush(q, (cnt + 1, n - 1))

  if n + 1 <= 100000 and dp[n + 1] >= cnt + 1:
    dp[n + 1] = cnt + 1
    heapq.heappush(q, (cnt + 1, n + 1))

  if n * 2 <= 100000 and dp[n * 2] >= cnt + 1:
    dp[n * 2] = cnt + 1
    heapq.heappush(q, (cnt + 1, n * 2))

print(min_cnt)
print(answer_cnt)

タイムアウトパーティー...