cafelier@SRM

SRM496

SRM | 16:21 |

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]) 文字のところで注意するだけ、なんですけど…ううーむ