Hatena::Grouptopcoder

cafelier@SRM

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

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

 | 

2011-02-11

SRM497

| 17:14 | はてなブックマーク - SRM497 - cafelier@SRM

SRM497 の成績・ソース (要ログイン) : AC/WA/- : ひどいタイポでした…

感想ログ疲れたので縮小運営中

250

class PermutationSignature { public:
   vector <int> reconstruct(string signature) 
   {
      deque<int> cur(1, 1);
      for(int i=signature.size()-1; i>=0; --i)
      {
         int ins = (signature[i]=='I' ? 1 : cur.front()+1);
         cur.push_front(ins);
         for(int k=1; k<cur.size(); ++k)
            if( cur[k] >= ins )
               cur[k] ++;
      }
      return vector<int>(cur.begin(), cur.end());
   }
}
  • I で始まるなら「最初を 1 にして残りを 2 ~ N で作る」が最適なのは明らか
  • DDD..DD (k個) で始まるなら「k+1 k k-1 ... 2 1 で始めて残りを残りを残りで頑張る」のが最適
  • というのをそのまま前からDを数えながら作ろうと思ったけど、微妙に面倒くさいなー
  • ということで、これは多分後ろから決めて行った方が楽な気がする
  • というのが上のコード
  • 二問目が550だったので250早解きゲーになるだろうと推測して、
  • ろくに後ろからで正しいか検証してないけどサンプルと長さ2までの全ケース通ったのでsubmit。あってた。

550

class CssRules { public:
   int getMinimalCssRuleCount(vector <string> xthml) 
   {
      tree virtual_root;
      {
         num_node = 0;
         string xs = accumulate(xthml.begin(), xthml.end(), string(""));
         const char* p = xs.c_str();
         virtual_root.children = parse_tags(p);
      }
      vector<int> memo(num_node*8*8*8, -1);
      return rec(virtual_root.children, 7*64+7*8+7, memo);
   }

   struct tree
   {
      int id;
      int tag;
      int color;
      vector<tree*> children;
      ~tree() { for(int i=0; i<children.size(); ++i) delete children[i]; }
   };

   // solver -------------------------------------------------------------

   int rec(vector<tree*>& ts, int tag_to_color, vector<int>& memo)
   {
      int sum = 0;
      for(int i=0; i<ts.size(); ++i)
         sum += rec(ts[i], tag_to_color, memo);
      return sum;
   }

   int rec(tree* t, int tag_to_color, vector<int>& memo)
   {
      const int key = t->id * 8*8*8 + tag_to_color;
      if( memo[key] >= 0 )
         return memo[key];

      int me   = ((tag_to_color>>(3*t->tag))&7) != t->color;
      int best = 0x3fffffff;
      for(int ttc=0; ttc<8*8*8; ++ttc)
      {
         int cost = 0;
         cost += ((tag_to_color>>0)&7) != ((ttc>>0)&7);
         cost += ((tag_to_color>>3)&7) != ((ttc>>3)&7);
         cost += ((tag_to_color>>6)&7) != ((ttc>>6)&7);
         best = min(best, cost + rec(t->children, ttc, memo));
      }
      return memo[key] = me + best;
   }

   // parser ------------------------------------------------------

   int num_node;

   vector<tree*> parse_tags( const char*& p )
   {
      vector<tree*> res;
      while(*p && p[1]!='/')
         res.push_back(parse_tag(p));
      return res;
   }

   tree* parse_tag( const char*& p )
   {
      static map<string, int> color_map;
      if( color_map.empty() )
      {
         color_map["black"]  = 0;
         color_map["blue"]   = 1;
         color_map["gray"]   = 2;
         color_map["green"]  = 3;
         color_map["red"]    = 4;
         color_map["white"]  = 5;
         color_map["yellow"] = 6;
      }
      static map<string, int> tag_map;
      if( tag_map.empty() )
      {
         tag_map["b"] = 0;
         tag_map["u"] = 1;
         tag_map["i"] = 2;
      }

      // <TAG id='ID' style='color:COLOR'>tagContent</TAG>
      p++;                                  // <
      string tag; while(*p!=' ') tag+=*p++; // TAG
      while(*p==' ') ++p;                   // _sp_
      p += 4;                               // id='
      string id;  while(*p!='\'') id+=*p++; // ID
      ++p;                                  // '
      while(*p==' ') ++p;                   // _sp_
      p += 13;                              // style='color:
      string cl;  while(*p!='\'') cl+=*p++; // COLOR
      p += 2;                               // '>
      vector<tree*> ch = parse_tags(p);     // tagContent
      p += 4;                               // </TAG>

      tree* t = new tree;
      t->id       = num_node++;
      t->tag      = tag_map[tag];
      t->color    = color_map[cl];
      t->children = ch;
      return t;
   }
};
  • 本番は 7*64+7*8+7 が 7*64+7*8*7 になっていて死亡
  • それ以前に、最初は pair< tree*, vector<int> > から int への map でメモっていたんだけど、提出してから最悪ケースを作ってみてTLEすることに気づいて再提出。
  • いろいろ酷い
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20110211
 | 

presented by cafelier/k.inaba under CC0