裏紙

ほぼ競プロ、たまに日記

AOJ 1275 - And Then There Was One

And Then There Was One | Aizu Online Judge

どうやら割と有名な問題らしい(ヨセフスの問題 - Wikipedia)。
考え方が印象に残ったのでざっくりメモ。

n人で構成された輪があり,はじめの基準位置の人(ここではNo.0と呼ぶ)からk-1だけ先にいる人(つまりNo.k-1)を処刑する。次に基準位置をNo.kとし,そこからk-1だけ先にいる人を処刑...と以下繰り返す。

はじめの基準位置がNo.0で,n人いてk人間隔で処刑していく時に,最後に残る人をNo.f(n,k)としよう。そのとき
f(1,k) = 0
f(n,k) = {f(n-1,k)+k} % n
となる。
1つ目の式は最初から1人しかいないからNo.0が生き残りになるということをいってるだけ,
2つ目の式はn人の輪とn-1人の輪の関係を考えてみればわかる。
n人からn-1人になる過程をみると,No.k-1が処刑されてn-1人になるということになる。つまり,1人減ると次の基準はNo.kになるのでkだけずらせば良いというはなし。で輪だから余りを取る。

最初,シミュレーションのような感じで人を減らして輪がどのようになるかを配列で管理するやり方で書いたが,O(n^2)になってしまいn<=10000で案の定間に合わなかった。

今回の問題は最初No.mを処刑し,そこからスタートとなる,人の番号が1~nとなっている,ということを考慮して,1人減らしてスタートをmにして,最後に1を加える,という感じでこれが完成した。

・実装

#include <cstdio>
#include <iostream>
using namespace std;

int f(int n, int k){
	if(n==1) return 0;	
	return (f(n-1,k)+k)%n;
}

int main(){
	while(1){
		int n, k, m;
		scanf(" %d %d %d", &n, &k, &m);
		if(n==0) break;
			
		printf("%d\n", (f(n-1,k)+m)%n+1);
	}
}