Python

🐒 ジョセフス問題

ジョセフス問題は以下の通りです.
1番からN番までは、N人が1つの円に座り、正の整数K(≦N)を与えます.今は順番にK人目を除いています.一人が取り除かれると、残りの人からなる円に沿ってこの過程が続きます.この過程はN人全員がクリアされるまで続く.円上の人々が消去される順序を(N,K)−ジョセフス配列と呼ぶ.例えば、(7,3)−ジョセフス配列<3,6,2,7,5,1,4>である.
NとKをあげると(N,K)-ジョセフスシーケンスを求めるプログラムを書きます.

の第1行において、NおよびKは、スペースを介して順次与えられる.(1 ≤ K ≤ N ≤ 5,000)

例に示すように、ジョセフスシーケンスが出力される.

入力例

7 3

出力例

<3, 6, 2, 7, 5, 1, 4>

私の草

from collections import deque

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

queue1 = deque()

output = []

for i in range(1,n+1):
    queue1.append(i)

while len(queue1) != 0:
    for _ in range(k-1):
        queue1.append(queue1.popleft())
    output.append(queue1.popleft())

print('<%s>' %', '.join(map(str, output)))

初めて問題に触れて、問題を理解するのに時間がかかったが、理解してからどうやって実現したのか思い出せなかった.
資料構造問題ライブラリでは、スタックやキューで解決すべきだが、思い出せない...
最後まで並ぶと、列の始まりに戻ると思っていたが、実現しなかった.
今回は30分も経ったので、解答を検索しました.
https://youjin86.tistory.com/18
こちらの解答を見てDeque()のrotate()メソッドを利用しました.

https://leonkong.cc/posts/python-deque.html
deque説明はマイクロブログを参照しています.
dequeはdouble-dend queueの略です.
双方向Qという意味で、スタックとQが合わさっています.
rotate()メソッドはdequeを回転します.
回転寿司を見たことがあるようです.
例を見ると何かわかるようですが、言葉では説明できません
私はまだrotate()を完全に理解していませんが、書きたくありません.
rotate()の説明を見ているうちに、私が理解できる方法を思いつき、再び解答に挑戦しました.
アイデア:キューデータ構造、popleft

from collections import deque

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

queue1 = deque()

output = []	# 제거되는 숫자를 담을 리스트이다.

for i in range(1,n+1): # 1부터 n까지의 숫자를 큐에 담는다.
    queue1.append(i)

while len(queue1) != 0: # 큐에 남은 값이 없으면 반복문을 종료한다.
    for _ in range(k-1): 
        queue1.append(queue1.popleft()) # 가장 왼쪽에 있는 값 하나를 떼와서 맨 뒤에 붙인다!
        			# 제거할 순번이 오기 '전' 까지 반복한다.
    output.append(queue1.popleft()) # 제거할 순번이 오면 큐의 가장 왼쪽 값 하나를 떼와서 출력할 리스트에 붙인다!
    

print('<%s>' %', '.join(map(str, output)))

第2セットは22分かかりました.
最後のprint()は、<>間で区切られた形式で出力する必要があります.
私ではなく、困っている人です.

正解…!はい、しかし、この問題の制限時間は2000ミリ秒です.
なぜ通過するのかと思った.
元々Pythonは運転速度が遅く、他の制限がないという問題で、
時間奨励を受けた後、Pythonの制限時間は(指定時間*3+2)秒です.
しかし、他の人の草よりも長い時間がかかります.
後で別の方法を知ったら、もう一度やってみます.