Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-07-01

SRM 474

| 17:43 | はてなブックマーク -  SRM 474 - cafelier@SRM

SRM 474 の成績・ソース (要ログイン) : AC/AC/TLE : そろそろvolatilityの低さで争いたくなってきた


500開く

  • 『連結な無向グラフが与えられます。頂点0からの最短経路木は何個ありますか。mod 1000000007で数えてね。』
    • サイズろくに見てないけど確か50頂点くらい

  • えーと、普通にDijkstraを走らせると最短経路木1つなら作れる。
  • で、Dijkstra やってる時に自由度がある部分、つまり
    • 既に最短経路が定まった集合から、次に近い頂点への最短路辺が複数出ている場合
  • こういう状況がある場合に、この自由度をひたすら掛け算してれば求まる、よね。


  • えーとpriority_queueを書いて
  • popした先頭だけじゃなくて、同じ距離になる候補はpopしまくって、
  • 自由度の分を掛け算しながらあとは普通にDijkstra

  • ううむけっこう時間かかってしまった。コーディング遅い。
  • sampleあったし、瞬殺しないといけない問題っぽいから即submitしちゃえ

250開く

  • すでにトップ10人くらいは250と500両方解いてる…250も瞬殺問題か。
  • 『10億次元くらいの空間の中を、どっかの座標を±1変える、という操作を最大50回行ってふらついてる人がいます。同じ箇所を2回通ったかどうか判定してね』

  • 10億次元のベクトルを本当にvectorで作る…わけにはいかないので
  • どうせ50座標しか動かさないのだから、その座標の情報だけ覚えておけばいい
  • map<int,int> でベクトルを表現
  • 指示どおり動かす
  • 50^2 で、同じ位置にきてないかmapを比較して判定
  • おわり。できた。

1000開く

  • 『N頂点のツリーをN頂点のグラフに埋め込みたい。やり方は何通り?mod 1000000007で。』
    • N≦14

  • テストケース作り
    • 最小例はN=1
    • 最大は…とりあえずグラフの側は完全グラフの方が埋め込みパターン数多いからそうしておこう
    • ツリーの側は、えーとツリーをこの入力の書式で書くのめんどいな
    • とりあえず0-1-2-3-...-13 みたく直線的につながってる例を入れておく

  • N=14ってすごく小さいな!
  • 2^N が余裕でできるレベル

  • ツリーはrootが頂点0であると見なすことにして
    • f(tv, gv, G)
    • を、「ツリーの頂点tvから始まるsubtreeを、tvをグラフの頂点gvに対応させつつ、グラフの頂点集合Gをぴったり使って埋め込むパターン数」とする
  • 答えは Σ_{gv∈グラフの全頂点} f(0,gv,グラフの全頂点)

  • これfの引数 N * N * 2^N 通りしかないのでメモ化再帰するだけじゃないですかね。
    • 14*14*16384。300万くらい。
  • 書き書き

  • ええと、tvの子供達にGを分割してあげなきゃいけないわけだよな。
  • Gのsubsetを列挙して、それでまあ適当に。
  • 子供のindexでもメモ化再帰するか。
    • g(tv,gv,G,i)
  • みたいな表

  • できた
  • しかしスピード怪しいなー
  • 表一個埋めるのにsubset列挙とかしてるから、
    • 14^3*(2^14)^2
  • くらいになってないか最悪

  • しかしとりあえずサンプルとさっき入れたデータは数百msで通った
  • とりあえずsubmitしちゃえー!

  • で、もっと酷い例は…
  • ツリーを普通にツリーっぽくしてみよう
  • 3分木っぽいのを入れてみた

  • うわー30秒くらいかかる
  • ダメだこれは

  • 色々改善策を考えるも思いつかず

撃墜タイム

  • 250も500もそんなに間違えるポイント無さそうだし
  • 1000のTLE狙いかな

  • お、自分と全く同じ方針っぽい人がいる
  • さっきの三分木を投入!
  • …あれ、間に合ってしまった。なぜだー -25

感想

  • スピードで負けてるなあ。ぬぬぬ
  • あと
    • for(subset=all; subset; subset=( (subset-1)&all ) )
  • と書いている人がいて、なるほどなあと感心している。こんどから使おう

SRM474 1000

| 13:29 | はてなブックマーク -  SRM474 1000 - cafelier@SRM

  • 大筋ではあってた。submitしたものから
    • メモ化の表をmapからvectorにして7倍速
    • subtreeのノード数と割り当てようとしているグラフのノード数が一致していることのチェックを、グラフノードからルートを割り当てるループより先に回したら4倍速
    • くらいで。まあ後者はそりゃそう書かなきゃだなあ。

template<typename T>
struct DP3
{
   int N1, N2, N3;
   vector<T> data;
   DP3(){}
   DP3(int N1, int N2, int N3, const T& t = T())
      : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
   T& operator()(int i1, int i2, int i3)
      { return data[ ((i1*N2)+i2)*N3+i3 ]; }
   void swap(DP3& rhs)
      { data.swap(rhs.data); }
};

class GameWithGraphAndTree { public:
   vector<string>        graph;
   vector< vector<int> > children;
   vector<int>           subtree_size;

   int calc(vector <string> graph_, vector <string> tree_) 
   {
      int N = graph_.size();

      graph = graph_;
      children.resize(N);
      subtree_size.resize(N);
      computeChildren(-1, 0, tree_);

      memo = DP3<LL>(N,N,1<<N,-1);

      LL answer = 0;
      for(int gv=0; gv<graph.size(); ++gv)
         answer += vertical(0, gv, (1<<N)-1);
      return int(answer % 1000000007);
   }

   void computeChildren(int tparent, int tv, const vector<string>& tree)
   {
      subtree_size[tv] = 1;
      for(int tc=0; tc<tree.size(); ++tc)
         if( tree[tv][tc] == 'Y' && tc!=tparent ) {
            children[tv].push_back(tc);
            computeChildren(tv, tc, tree);
            subtree_size[tv] += subtree_size[tc];
         }
   }

   LL vertical(int tv, int gv, int mask)
   {
      return horizontal(tv, gv, mask&~(1<<gv), 0); 
   }

   DP3<LL> memo;
   LL horizontal(int tv, int gv, int mask, int i)
   {
      if( i == children[tv].size() ) 
         return 1;
      int tu = children[tv][i];

      if( memo(tv,gv,mask) >= 0 )
         return memo(tv,gv,mask);

      LL answer = 0;
      for(int subset=mask; subset; subset=(subset-1)&mask)
         if( __builtin_popcount(subset) == subtree_size[tu] )
            for(int gu=0; (1<<gu)<=subset; ++gu)
               if( graph[gv][gu]=='Y' && ((1<<gu)&subset) )
                  answer += vertical(tu, gu, subset) * horizontal(tv, gv, mask&~subset, i+1);

      return memo(tv,gv,mask) = answer % 1000000007;
   }
};
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100701
 | 

presented by cafelier/k.inaba under CC0