cafelier@SRM

SRM497

SRM | 17:14 |

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することに気づいて再提出。
• いろいろ酷い