また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)
次で赤は十分に可能性ある。