今天早上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，再創歷史新高…………