cafelier@SRM

SRM500

SRM | 04:41 |

SRM500 の成績・ソース (要ログイン) : AC/TLE/- : 好きな問題セット。汚く書くと酷いことになりバグだらけとなるが整理して書けばバグる余地などなく綺麗になる、というのが顕著に出てくる問題が好きです。

500

class FractalPicture { public:
   double getLength(int x1, int y1, int x2, int y2) 
   {
      return rec(1, x1, y1, x2, y2);
   }

   double rec(int i, int x1, int y1, int x2, int y2)
   {
      x1 = clip<-27,+27>(x1);
      x2 = clip<-27,+27>(x2);
      y1 = clip<  0,+81>(y1);
      y2 = clip<  0,+81>(y2);

      if( i == 501 )
         return 0;
      if( x1<=-27 && 27<=x2 && y1<=0 && 81<=y2 )
         return 81 + (500-i)*54;
      if( x2<=-27 || 27<=x1 || y2<=0 || 81<=y1 )
         return 0;
      double L0 = (x1<=0 && 0<=x2 ? clip<0,54>(y2)-clip<0,54>(y1) : 0);
      x1=x1*3, x2=x2*3, y1=(y1-54)*3, y2=(y2-54)*3;
      double L1 = rec(i+1, x1, y1, x2, y2);
      double L2 = rec(i+1, y1, x1, y2, x2);
      double L3 = rec(i+1, y1, -x2, y2, -x1);
      return L0 + (L1+L2+L3)/3;
   }

   template<int m, int M>
   int clip(int v) { return max(m, min(v, M)); }
};

• 方針としては
  • そのまんま問題の定義通りに、3分岐で再帰して領域に入っている部分の長さを数える
• でよい。
• ただ、本当にそう書くと 3^500 分岐なので終わらないので、
  • 今注目しているnonfinalな線分を種とした図形が
    • 全く (x1,y1)-(x2,y2) の中に入らない == 即座に0を返す
    • 完全にすっぽり (x1,y1)-(x2,y2) の中に入る == 簡単な式で全部の長さが求まるので即座にそれを返す
• とする。
• 「線分の長さは1/3, 1/3, 1/3 になっていくので、すぐにどちらかのパターンに落ちる」ので大した分岐数にはならない

• 問題は、
  • 線分の端点の座標には次々1/3がかかっていくので、それをそのまま持って再帰しているとdoubleが計算に必要になって、
  • ちょっと余計なepsilonなどを入れて入れ方を間違えると、誤差などでどちらのパターンにもうまく落ちずに、もろに3^500再帰することがある。
  • という理由で本番submitしたコードではTLEで死亡
  • （おかしなepsilonの入れ方しなければ大丈夫っぽいですが…）
• 逆に考えて
  • 線分の座標は常に回転、拡大して (0,0)-(0,81) に正規化するようにして、bounding box の方も回転拡大するようにすれば、
  • こっちは3倍3倍なので常に整数座標で処理できる。
  • そうするべき。

250

class MafiaGame { public:
   double probabilityToLose(int N, vector <int> decisions) 
   {
      vector<int> vc;
      {
         map<int,int> voteCnt;
         for(int i=0; i<decisions.size(); ++i)
            voteCnt[decisions[i]] ++;
         for(map<int,int>::iterator it=voteCnt.begin(); it!=voteCnt.end(); ++it)
            vc.push_back( it->second );
      }
      const int MAX = *max_element(vc.begin(), vc.end());
      if( MAX == 1 )
         return 0.0;

      const int GotMAX = count(vc.begin(), vc.end(), MAX);
      for(int k=GotMAX; k!=1; k=(N-k*MAX)%k)
         if( k == 0 )
            return 0.0;
      return 1.0/GotMAX;
   }
};

• 全員1票以下なら下からuniform投票すると全員ピタリ1票になるので無限ループ
• それ以外の場合、鳩ノ巣原理より、下からuniform投票では0票が1票になることしかないので、
• 元々最大得票だった人だけが最終的に最大得票になる。これをGotMAX人とする
  • このGotMAX人は全員対等なので、求める確率は 1/GotMAX しか有り得ない。
  • 無限ループする0.0か、1/GotMAX かどちらかを判定すればよい
  • 固定票MAX票のk人が同率首位のとき、下から投票すうと(N-k*MAX)%k人が頭一つ飛び出すので…
  • というループを繰り返せば判定終わり
• 本番の時は、「元々最大得票だった人だけが最終的に最大得票になる」をコード書くまで気づけなかったのでだいぶ余分なコードを書いてしまった。