AOJ2119 Finding the Top RPS Player

AOJ Volume21

問題リンク Finding the Top RPS Player

  • 概要

N人の人を集め、じゃんけんを行う。
N人は最初0勝である。ゲームは1ターンに同時に任意の数だけ試合が行われる。ただし、試合は連勝数の等しい人同士のみ行う事が出来る。k連勝同士の人が試合をすると勝った方がk+1連勝となり、負けた人は0勝に戻る。
M連勝する人が現れるための最小ターン数を答えよ。
2 <= N <= 20
1 <= M < N

  • 解法

貪欲のようなシミュレートで解きました。
勝数が大きい人を1ターン中にたくさん作り出したいため、行える試合は全て行った方が得です。
c[M]: M連勝している人の人数
という表を作りながら1ターン毎に試合結果をシミュレートしていきます。
c[ ]が現在のターンで、この配列から次のターンの状態を表すnext[ ]を埋めます。
c[k]/2の人数だけ勝つのでnext[k+1]+=c[k]/2となります。同様に、c[k]/2の人数は負けるので、next[0]+=c[k]/2となります。見落としてはいけない点として、c[k]が奇数だった場合、試合をしていない人が1人残っているので、next[k]+=1となります。

  • ソース
import java.util.Arrays;
import java.util.Scanner;

//Finding the Top RPS Player
public class AOJ2119 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(int T=1;;T++){
			int N = sc.nextInt(), M = sc.nextInt();
			if((N|M)==0)break;
			int[][] c = new int[2][M+1];
			c[0][0] = N;
			for(int x=1,t=1;;t++,x=1-x){
				Arrays.fill(c[x], 0);
				for(int i=0;i<M;i++){
					c[x][i+1]+=c[1-x][i]/2;
					c[x][0]+=c[1-x][i]/2;
					c[x][i]+=c[1-x][i]-c[1-x][i]/2*2;
				}
				if(c[x][M]!=0){
					System.out.println("Case "+T+": "+t); break;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ2119().run();
	}
}