cafelier@SRM

SRM471 (ノーゲーム)

SRM | 02:21 |

• サーバトラブルで途中でarenaが落ちました
• 500, 250 をまあ普通に解いて50位くらい → 1000でうなっている最中におしまい
• コードだけ貼っておく
• （追記：どっちも通った）

250

• 『2で割る(余りは切り捨て)を0,1,2,...,D-1回繰り返しても素数な数のうち、N以下で最大のもの』
  • N≦1000万
  • D≦10

class PrimeSequences { public:
   int getLargestGenerator(int N, int D) 
   {
      int result = -1;

      vector<int> p(N+1, 1);
      p[0] = p[1] = 0;
      for(int q=2; q<=N; ++q)
         if( p[q] ) {
            for(int qq=q+q; qq<=N; qq+=q)
               p[qq] = 0;
            p[q] = p[q/2]+1;
            if( p[q] >= D )
               result = q;
         }

      return result;
   }
};

• submit したのはエラトステネスの篩と別にメモ化再帰で回してましたが、
• まとめたら綺麗かなあと思ってsubmit直後に整頓したもの。

• エラトステネスは普段
  • for(int q=2; q*q<=N; ++q) if(p[q]) for(int qq=q*q; qq<=N; qq+=q) p[qq] = 0;
  • こう書いてるんですけど素数に対しての処理をまぜるためにちょい無駄に色々回っている
• メモ
  • 素数の逆数和のオーダが O( log log n ) http://mathworld.wolfram.com/HarmonicSeriesofPrimes.html
  • なので、篩の計算量は O( n・log log n )くらい

500

• 『都市0から都市N-1まで有向グラフの上を最短で進みたい。ただしそのとき、パス上のどの都市to都市の連続区間の長さも13の倍数であってはならない』
  • N≦25

class ThirteenHard { public:
   int calcTime(vector <string> city) 
   {
      typedef int vert;
      typedef int cost;
      typedef pair<cost,vert> cedge;
      priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
      Q.push( cedge(0,1*32+0) );

      set<int> visited;
      while( !Q.empty() )
      {
         cedge s = Q.top();
         Q.pop();
         if( visited.count(s.second) )
            continue;
         visited.insert(s.second);

         int v    = s.second%32;
         int mask = s.second/32;
         int c    = s.first;
         if( v == city.size()-1 )
            return c;

         for(int i=0; i<city.size(); ++i)
         {
            char dd = city[v][i];
            int d = ('a'<=dd && dd<='z' ? dd-'a'+27 : dd-'A'+1);
            if( dd!='#' && d%13>0 )
            {
               int mask2 = mask << (d%13);
               if( mask2 & (1<<13) )
                  continue;
               mask2 = (mask2 & ((1<<13) - 1)) | (mask2 >> 13) | (1<<d%13);
               int s2 = mask2*32 + i;
               if( !visited.count(s2) )
                  Q.push( cedge(c+d, s2) );
            }
         }
      }
      return -1;
   }
};

• 25 * 2^13 (今いる都市 * 今いる都市までの区間長の余りの集合⊆{0,1,2,...,12}) 頂点のダイクストラ
• 辺数が最大 25*(25*2^13)=512万 だし全部行き尽くすことはないだろうから
• 十分間に合うかなーと（試してない）
  • practiceで通してみたら100msもかからなかった
  • 余り0って最初しか使わないから 25*2^12 か。

1000

• 『N本の3次元の線分がくるので自己交差しないように全部順番につなぎ合わせて一つの折れ線にして、端と端が一番遠くなるようにしてね』
  • N≦50

• それぞれどっち向きで足すかを ai∈{+1,-1} として
• (Σai・vi)^2 の最大化
• たぶん最大のときは自動的に自己交差がない…はず…。でないと解ける気がしない
• (Σai・vi)^2 = Σvi^2 + 2Σai・aj・vi・vj
• なので、内積vi・vjを重みwij として、
• Σai・aj・wij
• を最大化する。
• Σwij - 2Σ_{i,jが違う部分}wij
• だからaiとajが違うところだけwijのコストがかかる感じなので
• なんかこう、辺の重みwijの無向完全グラフの最小カットとかになったり…
• とりあえず最小カットライブラリコピペして使ってみる
• 全然ダメ
• そもそも負の重みとか対応してたっけこれ…？
• とかやってるうちにタイムアップ