Josephus Permutation

問題文 : Josephus Permutation

解法 :

アルゴリズムイントロダクションに乗っていた問題を実際にコードに起こしたもの.
ヨセフスの芋の軌跡をたどったものを出力する問題.
愚直にm % n 個先までたどる線形リストなどではO(n^2) となり. TLE するだろう. そこで, セグメント木を用いて高速化する(BIT をたどっている感じなのでBIT でもできそうだが).

もし, 今いる位置から先にm % n 個の数値があれば, その位置をセグメント木をたどりつつ求める. そうでなければ, m % n - (今いる位置から先の個数) を先頭から求める.

計算量はO(n log n) となる. 本当は制約をn ≦ 10^6 としたかったが, 全部を出力すると死んでしまうのでn ≦ 10^5 とした. (k 番目を出力でもよかったが.

コード :

#include <cstdio>

int seg[1 << 18];

void add(int k, int x)
{
	k += (1 << 17) - 1;
	seg[k] += x;
	while (k){
		k = (k - 1) >> 1;
		seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2];
	}
}

int findPos(int x, int c = 0, int k = 0, int l = 0, int r = 1 << 17)
{
	if (c + seg[k] == x && r - l == 1) return (l);
	if (c + seg[k * 2 + 1] < x)return (findPos(x, c + seg[k * 2 + 1], k * 2 + 2, (l + r) / 2, r));
	return (findPos(x, c, k * 2 + 1, l, (l + r) / 2));
}

int getSum(int a, int b, int k = 0, int l = 0, int r = 1 << 17)
{
	if (b <= l || r <= a) return (0);
	
	if (a <= l && r <= b) return (seg[k]);
	
	return (getSum(a, b, k * 2 + 1, l, (l + r) / 2) + getSum(a, b, k * 2 + 2, (l + r) / 2, r));
}

int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) add(i, 1);
	
	int pos = 0;
	for (int i = 0; i < n; i++){
		int x = m % (n - i) ? m % (n - i) : n - i;
		if (getSum(pos, n) >= x) pos = findPos(x + getSum(0, pos));
		else pos = findPos(x - getSum(pos, n));
		
		printf("%d%c", pos + 1, i == n - 1 ? '\n' : ' ');
		add(pos, -1);
	}
	
	return (0);
}

ほそく :
一番最後に処刑される人は, f(n, k) = (n, k) - Josephus Permutation の最後の項とすると,
f(n, k) = (k + f(n, k - 1)) % n で求まる.0 - indexed として, 位置 k を初めとする(n - 1, k) - Josephus permutation の最後の項が新しい最後の位置となる.
これはO(n) で計算できる.

#include <cstdio>

using namespace std;

int findLast(int n, int k)
{
	if (n == 1) return (0);
	return ((findLast(n - 1, k) + k) % n);
	//k-th person will be sacrifised.
}

int main()
{
	int n, k;
	
	scanf("%d %d", &n, &k);
	
	printf("%d\n", findLast(n, k) + 1);
}