SRM BrushUp: probabilityToLose (500 div2 Middle)

正答率5%以下の難問だったらしい。

私も本番では解けなかった。。（ちょっと言い訳をすると、飲みに行った後のSRMだったので・・。笑）

今日、落ち着いて解いてみたら普通に解けました。

でも反省すべきところはあります。

本番は、問題の意味を追うのに必死になって問題文を何回も読んでいました。

これは明らかに時間の無駄。

問題文がよく分からないときは、サンプルを読んで、紙と鉛筆でシミュレーションすればどうすればいいのか分かります。

これは、大事なSRM攻略法の一つな気がしますね。。

この問題のポイントは、

• 決定権のある人が投票し終わった時点で、最大票を集めた人の投票数が1の場合は無限ループ
• 決定権のある人が投票し終わった時点で、最大票を集めた人が1人しかいない場合はその人が絶対選ばれる
• それ以外の場合は投票対象が縮小される。⇒縮小はモジューロ演算を使えばよい

です。下手に難しく考えすぎるとhogeってしまうので、div2の500なんでそんな難しくはないだろうっていう気持ちで臨むことも大事だと思いました。

ソースはこちら。最近よく見るrngさんのコーディングスタイルにちょっと影響された（笑

view plainprint?

1. class MafiaGame {  
2. public:  
3.     double probabilityToLose(int N, vector<int> decisions) {  
4.         int M = decisions.size();  
5.         int point[N];  
6.   
7.         fill(point, point+N, 0);  
8.         REP(i, N) REP(j, M) if (decisions[j] == i) ++point[i];  
9.   
10.         int mx = *max_element(point, point+N);  
11.         if (mx == 1) return 0.0;  
12.   
13.         int cnt = 0;  
14.         REP(i, N) if (point[i] == mx) ++cnt;  
15.         if (cnt == 1) return 1.0;  
16.   
17.         double ret = 1./cnt;  
18.         while (1) {  
19.             int rm = N - mx * cnt;  
20.             if (rm % N == 0) return 0.0;  
21.             cnt = rm % cnt;  
22.             if (cnt == 1) break;  
23.         }  
24.         return ret;  
25.     }  
26. };  

class MafiaGame {
public:
    double probabilityToLose(int N, vector<int> decisions) {
        int M = decisions.size();
        int point[N];

        fill(point, point+N, 0);
        REP(i, N) REP(j, M) if (decisions[j] == i) ++point[i];

        int mx = *max_element(point, point+N);
        if (mx == 1) return 0.0;

        int cnt = 0;
        REP(i, N) if (point[i] == mx) ++cnt;
        if (cnt == 1) return 1.0;

        double ret = 1./cnt;
        while (1) {
            int rm = N - mx * cnt;
            if (rm % N == 0) return 0.0;
            cnt = rm % cnt;
            if (cnt == 1) break;
        }
        return ret;
    }
};