[python]白駿11866号:ジョセフス問題0

6890 ワード
コーディングテスト練習 インプリメンテーション パイ Deque テキストリンク

https://www.acmicpc.net/problem/11866

に答える


  • deque.回転の使用
    Dequeのrotate関数を使用すると、リストをnの左側(-n)右側(+n)に移動できます.
    これによりk番目の数字を一番前にシフトし、左から右へ順番に減算することができます.

  • Dequeを使用しない
    Dequeで表現して、終わった時に何も学んでいないと感じたので、書かずに体現しました.
    k番目の数字を削除するとインデックスも減少するので、kを付けて1を削除します.
    インデックスの範囲を超えないように、リストの全長を除いた値を使用します.20ミリ秒短縮

    • コード#コード#


    deque.回転の使用

    import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int,input().split())
circle = deque([x for x in range(1,n+1)])
removed = []
while circle:
    circle.rotate(-(k-1))
    removed.append(circle.popleft())
print(f'<{", ".join(map(str,removed))}>')

    Dequeを使用しない

    import sys
input = sys.stdin.readline
n, k = map(int,input().split())
circle = [x for x in range(1,n+1)]
removed = []
now = k-1
while circle:
    removed.append(circle.pop(now))
    if circle:
        now = ((now-1) + k) % len(circle)
print(f'<{", ".join(map(str,removed))}>')
    try catchネスト実行順序テスト
    Elixir:Doctest,APIドキュメントに直接テストを記述する