Joseph's Potato [AOJ0085]

ヨセフのおイモ | Aizu Online Judge

package Blog;

import static java.lang.System.*;
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		while(sc.hasNext()) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if (n==0 && m==0) break;
			
			LinkedList<Integer> list = new LinkedList<>();
			for (int i=1; i<=n-1; i++) list.add(i);
			list.addFirst(n);
			
			list.addLast(list.removeFirst());
			while (list.size() != 1) {
				for (int i=0; i<m-1; i++) list.addLast(list.removeFirst());
				list.removeFirst();
			}
			
			out.println(list.getFirst());
		}
	}
}

この問題では、配列ではなくリング構造を使ったほうが分かりやすそうだったので、LinkedListを使って解いてみました。

・list.addLast(list.removeFirst());

の部分が、「先頭の要素を末尾に追加する」操作、いわば「リングを回す」操作になっています。問題においては「イモを右の人に渡す」操作ですね。

m回目に渡された人を除外する、という操作は、

・list.removeFirst();

の部分です。

除外するという操作の関係上、初回のイモ渡しのみループの外で行っています。

今回の問題では制約がm,n<1000と小さかったのでシミュレーションしましたが、これがもっと大きい場合は何か法則性を見つけて数学的に解く必要がありそうです。

リング構造が必要とされる問題はいままでほとんど解いたことがなかったのですが、今回のようにLinkedListを使うと簡単に解けそうなので、覚えておきたいです。