Hatena::Grouptopcoder

cafelier@SRM

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

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

 | 

2011-02-04

SRM496

| 16:21 | はてなブックマーク - SRM496 - cafelier@SRM

SRM496 の成績・ソース (要ログイン) : AC/AC/WA : 950点どころか95点でいいだろ、といいながら40分で実装できなかった死にたい

950

class YetAnotherHamiltonianPath { public:
   int leastCost(vector <string> label) 
   {
      int cost = 0;
      for(int i=0; i<label.size(); ++i)
         cost += label[i].size()*label[i].size() * (i<=1 ? 1 : 2); // どうやってもかかる分のコスト
      return cost - radixSort(label); // あとは max (Σ LCP^2) を引き算
   }

   int radixSort(const vector<string>& v, int i=0, bool single=true, bool hasBothZeroOne=true)
   {
      // 原則的に、0文字目が同じものどうしを一カ所にまとめた方が当然ベター
      // 0文字目が同じ中では1文字目が同じものどうしを一カ所に…という再帰
      map< char, vector<string> > classify;
      for(int k=0; k<v.size(); ++k)
         classify[v[k].c_str()[i]].push_back( v[k] );

      // N 個のブロックに分かれたら、分かれ目ではLCPが i なので、その分の Σ LCP^2 は i*i*(N-1)。
      int score = i*i * (classify.size()-1); 

      // あとはブロックごとに再帰的に LCP^2 の和を求めて足していく
      for(map<char, vector<string> >::iterator it=classify.begin(); it!=classify.end(); ++it)
      {
         bool sgl = single && classify.size()==1;
         bool hzo = hasBothZeroOne && it->first==v[0].c_str()[i] && it->first==v[1].c_str()[i];
         if( it->first )
            score += radixSort( it->second, i+1, sgl, hzo );
         else
            score += i*i * (it->second.size()-1 + (sgl?1:0) - (hzo?1:0));
      }

      // ただし、label[0] と label[1] が生き別れになる分かれ目は(最初から分かれてるので)数えない
      if( hasBothZeroOne && v[0].c_str()[i]!=v[1].c_str()[i] ) score -= i*i;

      // 逆に、全体が2つ以上のブロックに分かれるときには label[0] と label[1] の間に挟まるので
      // ΣLCP^2 がその分多い
      if( single && classify.size()>1 ) score += i*i;

      // 以上
      return score;
   }
};
  • label[0] と label[1] の1文字目が違えばソートするだけ。
  • そうでなくても、LCP(label[0], label[1]) 文字のところで注意するだけ、なんですけど…ううーむ
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20110204
 | 

presented by cafelier/k.inaba under CC0