説明:

これはプログラマーのジャンプと瞬間移動題です.一定の距離を移動する必要がある場合、1セルを消費して前に移動できるセットや、これまで行った距離の2倍の位置まで無料で送ることができる場合、指定距離の最小バッテリー代まで移動できるという問題があります.
无料のテレックスってどういう意味ですか、このセットを着て移动する距离は3日から6日まで无料で移动できます.では、電池を消費する必要はなく、格を移動する必要はなく、電話だけでいいのではないでしょうか.
しかし、始点での移動距離は0であるため、いくら電話をかけても0*2=0までは移動できない.したがって、少なくとも1回移動する必要があり、2倍移動するテレビポートの特性上、2の平方数しか達成できない.
問題は、その位置に正確に移動することを要求します.5の距離を移動する必要がある場合は、5の電池を消費し、15=5を移動し、1つの格子だけを移動し、2回のテレビポート、すなわち12*2=4を移動し、さらに1つの格子を移動し、電池は2を消費し、5を移動する.とにかく、目を越えてはいけない.

に答える

再帰DFSナビゲーション(再帰制限を超えている)

最初に試みた方法はDFSを用いてグラフィックを描画し探索することである.まず1コマ移動してから消費電池に戻り、さらに1コマ移動して電池を消費せず、現在位置で電話で送信する場合は分岐して再帰的に送信する.
問題の条件自体は複雑ではないので容易に実現できるが,問題が与えられる目的地距離は10000000,すなわち1億であることは無視できる.
実際,上記のようにコードを記述した結果,テストケース(5000)にも合格しなかったため,コードを再記述する必要がある.

minimum_battery_use = None

# 재귀 호출되는 DFS 함수
def move(battery_use, current_position, destination):
    global minimum_battery_use
    # 현재 이동거리가 목적지와 동일한 경우 배터리 최소 소모값 갱신
    if current_position == destination:
        minimum_battery_use = min(minimum_battery_use, battery_use)
    # 아직 목적지에 도착하지 않은 경우 계속 이동
    elif current_position < destination:
        # 배터리를 소모하고 한 칸 앞으로 이동
        move(battery_use+1, current_position+1, destination)
        # 배터리를 소모하지 않고 현재 위치의 두 배 위치로 텔레포트
        move(battery_use, current_position * 2, destination)
    

def solution(n):
    global minimum_battery_use
    minimum_battery_use = n
    # 일단 한 칸은 이동하고 시작해야 한다.
    move(1, 1, n)

    return minimum_battery_use

キューBFSでのナビゲート(タイムアウト)

2つ目の試みの方法は,キューを用いてBFS探索を行うことである.キューは、削除操作が頻繁であるため、O(1)速度を有する集合モジュールのdequeクラスを使用する.
しかし、DFSからBFSへの変更だけでは5000件のテストケースに合格できない.そこで,現在のバッテリ消費量が他のノードで測定した最小バッテリ消費量よりも大きい場合は,探索を行わずに停止する最適化方法を考えた.backtrackingという名前かどうかはよく覚えていませんが、いずれにしても、テストケースに合格すれば、精度テストにも合格できます.

from collections import deque


def solution(n):
    minimum_battery_usage = n
    queue = deque() # BFS 탐색을 위한 큐(데크)
    queue.append((1, 1)) # 현재 배터리 사용량, 현재 위치 튜플
    
    while queue:
        current_battery_usage, current_position = queue.popleft()
        # 현재 배터리 사용량이 최소 배터리 사용량을 초과하는 경우 무시
        if current_battery_usage > minimum_battery_usage:
            continue
        
        # 목적지에 도달한 경우 최소 배터리 사용량 갱신
        if current_position == n:
            minimum_battery_usage = min(minimum_battery_usage, current_battery_usage)
        elif current_position < n:
            # 목적지에 도달하지 못한 경우 이동, 텔레포트 BFS
            queue.append((current_battery_usage+1, current_position+1))
            queue.append((current_battery_usage, current_position * 2))

    return minimum_battery_usage

しかし、効率性テストはすべて合格しなかった.問題の特徴のため、グラフを探索する上で一定の限界がある.どうやって解くの?

さんじゅつえんざん

この接着剤はここからインスピレーションを受けた.
問題の最も重要な特徴は、現在の位置の2倍の位置に移動したテレビポートがバッテリを消費しないことです.では、すべての目的地ができるだけ多くの電話ポートで移動できれば、バッテリー消費を最小限に抑えることができますか?
しかし,すべての目的地は2の平方数ではないので,目的地から逆順探索を開始し,最大2の平方数で移動する計算過程が必要である.そこで私が考えている方法は、目的地の距離を2に分けて、離れない、つまり、2の平方数でなければバッテリー移動を消費し、その他の場合はテレビポートを使用せずにバッテリーを消費することです.
1から2にかけて開始するよりも、目的地から2に分けて、必要に応じて1格移動するのが最適化された方法です.テストケースとしての5000を例に挙げます.

5000

2500

1250

625

312.5

2にかかわらず、電話だけでは移動できません.

312から624に電報が送られ、1回移動する.

312

156

78

39

19.5

2にかかわらず、電話だけでは移動できません.

19から38に電報が届き、一度移動します.

19

9.5

2にかかわらず、電話だけでは移動できません.

9から18に移動し、1回移動します.

9

4.5

2にかかわらず、電話だけでは移動できません.

4から電話で8に移動し、一度移動します.

4

2

1

OK!
これで全部で4回直接移動し、1回目の移動回数を加えることで、5回、つまり5倍のバッテリーを消費し、5000個の距離を移動することができます.

これに基づいて作成されたコードは次のとおりです.

def solution(n):
    ans = 1

    while n > 1:
        n = n / 2
        if round(n) != n:
            ans += 1
            n = int(n)

    return ans

ポスト

最初はDFSやBFSのような探索問題だと思っていたが、かえって数学に近い問題だった.プログラマーのサマー符号化の他の問題も数学的な問題があるようだが、サマー符号化の特徴かもしれない.
テレビポートを使えば無料で移動でき、2倍移動できるという点に集中しているはずです.