SRM 575

またVasyl[alphacom]。今度はテストケースを作るのミスったらしいので、明らかにVasylが悪い。

250:
解法：奇数と2^n(nは奇数)はBrus,他はJohnであることが帰納法で分かる。
意外と時間がかかりました。

public class TheNumberGameDivOne{
	public String find(long a){
		if(a%2==1)return "Brus";
		int count=0;
		while(a>0&&a%2==0){
			a/=2;
			count++;
		}
		if(a==1&&count%2==1)return "Brus";
		return "John";
	}
}

500:
解法：最初と同じものが残っている確率をDP,残ってないなら他の数字が均等に存在している。これを求めたらあとは掛け算をする。
意外と時間がかかり、結構あせりました。testcase 64が変だったのでrejudgeが入る予定です。

public class TheSwapsDivOne{
	public double find(String[]a,int b){
		String c="";
		for(int i=0;i<a.length;i++)c+=a[i];
		int []d=new int[c.length()];
		for(int i=0;i<c.length();i++)d[i]=(int)(c.charAt(i)-'0');
		int sum=0;

		int n=d.length;
		for(int i=0;i<n;i++)sum+=d[i];
		double dp[][]=new double[b+1][2];
		dp[0][0]=1;
		dp[0][1]=0;
		for(int i=0;i<b;i++){
			dp[i+1][0]=dp[i][0]*(n-2)/n+dp[i][1]*2.0/n/(n-1);
			dp[i+1][1]=dp[i][0]*2/n+dp[i][1]*(1.0-2.0/n/(n-1));
		}
		double ret=0;
		for(int i=0;i<n;i++){
			ret+=(dp[b][0]*d[i]+dp[b][1]*(sum-d[i])/(n-1))*(i+1)*(n-i);
		}
		return ret*2/n/(n+1);
	}
}

1000:無理
Challenge Phase:
Easyで2の累乗ならばBrus、としている人がいたので16を投げた
Systest:
通る。みんな落ちているらしいが、多分あとで修正されるので順位は下がる。
Rating:
2081 -> 2148 (-33)

次で赤は十分に可能性ある。