今天早上0：00，SRM500……
注册时，定睛一看，有个TC的Member阵亡了…你是否同意把这次比赛奖金捐给他…本以为是11区人在海啸中阵亡，没想到是俄罗斯人，据传闻说是劳累过度之类的……（大帝：你看看，你看看，又是听说 =_=），讽刺的是这条新闻正文里面套着FB，然后墙了…………
不过奖金啥的也只能YY了……
250是个很硬的题……前几名里都有人彻底放弃了的……System挂掉了至少100人……
题意是这样：给N个人（N<=500），需要投票选出一个，其中M（M<=min(50,N)）人有确定的想法，其他人投票只投给当前票数最少的人，如果平票则在平票人中投第二轮，第三轮，原先如果有人确定想投某人，但是这人没晋级下一轮，则之后他就成无想法了………这样肯定有一些人被选出来的概率比较大，求最大的概率
Sample：
3
{1, 1, 1}
答案：1，1号一定被选出
5
{1, 2, 3}
答案：0，不可能选的完
（投完123后，人的得票数为01110，剩下两个，一个投0一个投4，又从头来了……）
20
{1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 18, 19, 0}
答案：0，第一轮：1234567，第二轮：剩下其中的6个，第三轮：剩下两个，第四轮就选不出来了……
23
{17, 10, 3, 14, 22, 5, 11, 10, 22, 3, 14, 5, 11, 17}
答案：0.142857.....，第一轮剩下7个，第二轮剩下2个，第三轮能选出来1个，每个人被选出的概率都是一样的……
这个问题不太好理解，多数人都卡在了读题上……而且很容易没有想法……
先写了个模拟，然后逐渐摸清门道了……
当时发现，前几轮的走势是必然的，后面的就有随机性了
譬如
20
{1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 18, 19, 0}
第一轮剩下的人，必然是1234567，但是后面，支持1234567的那14个人一定会给他们投票；其他6个没想法的人就不一定投给谁了…
于是先模拟出来那些必然现象，然后，就是纯粹和数字相关，和人无关的这么一件事情了……
大概就是N个人，M人候选这样……由于N个人中，包含M＊X个有想法的人，会给这M人分别投M票，剩下N－M＊X个没想法的人会给票少的人投，最后，下一轮的候选人就是N％M……一个小递归验证就行了……如果当前M可以得到1，则有解，如果最后N％M ＝＝ 0，就是上面那种20个人给2个人投票那样，投不出来……
事后看了别人的代码想明白了，只需要模拟一步……
代码：
1 class MafiaGame {
2 public double probabilityToLose(int N, int[] decisions) {
3 int[] cnt = new int[N];
4 int NoIdeaMan = N;
5 for (int i :decisions) {
6 cnt[i] ++;
7 NoIdeaMan --;
8 }
9 while (NoIdeaMan-->0) {
10 int min = 99999999;
11 for (int i : cnt) {
12 if (i < min) min = i;
13 }
14 for (int i = 0; i < N; i++) {
15 if (cnt[i] == min) {
16 cnt[i] ++;
17 break;
18 }
19 }
20 }
21 int Group = 0;
22 int max = 0;
23 for (int i : cnt) {
24 if (i > max) {
25 max = i;
26 Group = 0;
27 }
28 if (i == max) {
29 Group ++;
30 }
31 }
32 System.out.println(Group);
33 if (check(N,Group)) {
34 return 0.0;
35 }
36 return 1.0/Group;
37 }
38
39 boolean check(int N,int Group) {
40 if (Group == 1) return false;
41 if (N % Group == 0) return true;
42 return check(N,N%Group);
43 }
44 }
最后Systemtest阶段，哥从400＋爬到了324……前面至少挂了100人……
rating -> 1591，再创历史新高…………