AOJ2330 Earth Invasion Diary of Miyabi-sensei

問題リンク Earth Invasion Diary of Miyabi-sensei

• 解法

F(n)をn人のドラキュラの中から本物を見つけるための比較回数とします。
n < n'のとき、F(n) <= F(n')はすぐ分かると思います。
ここで、n人の中からx人だけ1つの皿の上に乗せると考えると、n人の集団が(x, x, n-2*x)の集団に分かれます。この集団に分けるために比較を1度行ったことになります。更に、比較の結果、本物のドラキュラがどの集団に属するかも分かります(天秤が振れたらxの中に、平衡したらn-2*xの中に居ると分かります)。最悪の比較回数はF(x), F(n-2*x)のうちの大きい方となります。よって、最悪の回数を押さえるためにはxとxとn-2*xの3つの集団の人数を平均的にすればいいと分かります。つまり、だいたいn/3の人数にすれば最悪の比較回数が抑えられることになります。あとは、n%3で少し場合分けを考えれば解けます。

• ソース

import java.util.Scanner;

//Earth Invasion Diary of Miyabi-sensei
public class AOJ2330 {

	int f(int n){
		return n<=1?0:(n%3==0?f(n/3):f(n/3+1))+1;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		System.out.println(f(sc.nextInt()));
	}
	
	public static void main(String[] args) {
		new AOJ2330().run();
	}
}