cafelier@SRM

SRM 474

SRM | 17:43 |

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

500開く

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

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

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

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

250開く

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

• 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 |

• 大筋ではあってた。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;
   }
};