2021-06-03 · 2분

BOJ 1158 — ヨセフス問題

algorithmboj

この記事は公開から2年以上経過しています。

BOJ #1158 問題：https://www.acmicpc.net/problem/1158

[アルゴリズム] - キュー（queue）で学んだキューを活用して問題を解決します！

問題解決

計算機科学や数学において、ヨセフス問題（Josephus problem）あるいはヨセフス順列（Josephus permutation）は次のように定義される。

n と k が自然数で、k < n と仮定する。n 人が円になって集まっているとき、任意の 1 人から順に数えていき、k 番目の人を集まりから除外する。残った n-1 人から再び次の人から順に数え、k 番目の人を除外する。これを誰も残らなくなるまで繰り返す。このとき集まりから除外される人の順を (n, k) ヨセフス順列といい、最後に除外される人を求める問題をヨセフス問題という。

解法の過程

C++ STL で提供される queue を使った。

(7, 3) のとき

(1, 2, 3, 4, 5, 6, 7) ( )
(1, 2, 4, 5, 6, 7) ( 3 )
(1, 2, 4, 5, 7) ( 3 , 6 )
(1, 4, 5, 7) ( 3 , 6, 2 )
(1, 4, 5 ) ( 3, 6, 2, 7 )
(1, 4 ) ( 3, 6, 2, 7, 5 )
( 4 ) ( 3, 6, 2, 7, 5, 1 )
( ) ( 3, 6, 2, 7, 5, 1, 4 )

N-1 回まで push してから pop し、

N のときは front してから pop を繰り返せば解決しそうです。

コード

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

int main() {
    int N, K;
    queue<int> Queue;

    scanf("%d%d", &N, &K);
    fgetc(stdin);

    for (int i = 1; i <= N; i++)
    {
        Queue.push(i);
    }
    printf("<");
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < K - 1; j++)
        {
            Queue.push(Queue.front());
            Queue.pop();
        }

        printf("%d", Queue.front()); printf(", ");
        Queue.pop();
    }
    printf("%d", Queue.front());
    printf(">\n");
    return 0;
}