[BOJ]#20055コンベアのロボットPython


質問する


https://www.acmicpc.net/problem/20055
長さNのベルトコンベアがあり、長さ2 Nのベルトコンベアは上下にベルトコンベア回りに回転する.ベルトは1の長さ間隔で2 N個の格子に分けられ、各格子には1から2 Nの番号があり、下図のようになっています.

ベルトが1マス回転すると、1番から2 N-1番のマスが次のマスの位置に移動し、2 N番のマスが1マスの位置に移動します.i号車の耐久度はAiです.上図では、1番欄の位置を「上へ移動位置」、N番欄の位置を「下へ移動位置」と呼びます.
コンベアに箱状のロボットを置きたいです.ロボットは上の位置にしか置けません.いつロボットが降りる位置に着いても、すぐに降ります.ロボットはコンベアで自分で移動できます.ロボットをある位置に上げたり、ロボットがある格子に移動したりすると、格子の耐久度がすぐに減少します.
コンベアでロボットを反対側に移動するつもりです.ロボットを動かす過程で、以下のことが順次発生します.
  • ベルトは、各車両の上のロボットとともに1つの車両を回転させる.
  • 最初にベルトをつけたロボットから、ベルトが回転する方向に1マス移動できるようになったら移動します.移動できないなら、おとなしくしています.
    2.1ロボットが移動するには、移動する格子にロボットがなく、格子の耐久度が1以上でなければなりません.
  • アップロード位置の格子耐久度が0でない場合は、ロボットをアップロード位置にアップロードします.
  • 耐久度が0の格子数がK個を超えると、プロセスは終了する.さもないと1番に戻ります.
  • 終了時にいくつかのステップが進行中であることを理解してみましょう.最初のステップは最初のステップです.

    入力


    1行目はN,Kである.2行目はA 1,A 2,...,A 2 Nへ

    しゅつりょく


    出力ステップ数が進行中に終了するかどうか.

    アイデア


    コンベアをdequeで作り、ロボットの位置を表すロボットもdequeで作ります.問題では所定の順序で実現する.
    ✔¥コード説明
    1.所定の終了条件に達するまで問題を繰り返す.

  • queueもrobotも最初は格子を回転させます.
    =>一番後ろの要素を削除し、一番最初に挿入します.

  • anyを使用して、ロボットが1つあれば動作します.( anyの使用 )
    3.1ロボットは降車位置で降りる.
    3.2ロボットが異なる位置にある場合は、1つずつ検査を行います.
    (nから2 nまでの位置にロボットが存在するはずがない=>ロボットが下降した位置にいるとすぐに下降するから)
    3.3ロボットが存在し、次の位置にロボットがいない場合、次の位置の耐久度が1より大きい場合にロボットを移動します.移動時に下がる位置であれば、ロボットを置きます.

  • 一番前の位置(上向きの位置)が0でない場合は、ロボットを1つ上げて耐久性を減らします.

  • 耐久度が0のものがkより大きい場合は、直ちにステップを終了して出力する.
  • マイコードpython

    from collections import deque
    
    n, k = map(int, input().split())
    queue = deque(list(map(int, input().split())))
    robot = deque([0] * n * 2) #로봇이 존재하면 1, 없으면 0
    ans = 0
    
    while True:
        ans += 1
        #컨베이어 벨트를 회전시킨다.
        queue.appendleft(queue.pop())
        robot.appendleft(robot.pop())
        if any(robot):  #로봇이 있으면 이동하기
            if robot[n-1] == 1: #내리는 위치에 있으면 바로 내린다.
                robot[n-1] = 0
            for i in range(n-2, -1, -1):    #하나씩 검사해서 이동 가능하면 이동시킨다.
                if robot[i] == 1 and robot[i+1] == 0 and queue[i+1] >= 1:
                    if i+1 != n-1:  #이동한 위치가 내리는 위치이면 바로 내린다.
                        robot[i + 1] = 1
                    robot[i] = 0
                    queue[i+1] -= 1
        if queue[0] != 0:   #맨 앞에 로봇을 올리수 있으면 올린다.
            robot[0] = 1
            queue[0] -= 1
        if queue.count(0) >= k: #내구도가 0인 것이 k개 이상이면 중단한다.
            print(ans)
            break