今日のTopCoder

TopCoder

問題文：http://www.topcoder.com/stat?c=problem_statement&pm=8160&rd=12170

C++で書いてはまったのでPythonで書き直した。

>>> def bar(s, c):
    result = []
    start = s.find(c)
    while start != -1:
        result.append(start)
        start = s.find(c, start + 1)
    return result

>>> bar("babab", "a")
[1, 3]
>>> def foo(w, words):
    can = dict((x, 0) for x in bar(words[0], w[0]))
    for i in range(1, len(words)):
        poss = bar(words[i], w[i])
        newcan = {}
        for p in poss:
            for k in can:
                if p <= k:
                    diff = k - p
                    score = can[k] + diff
                    if newcan.get(k, 10000) > score:
                        newcan[k] = score
                else:
                    diff = p - k
                    score = can[k] + diff * i
                    if newcan.get(p, 10000) > score:
                        newcan[p] = score
        can = newcan
    return can

>>> foo("abc", ["cacac", "cbbaa", "cc"])
{1: 0, 2: 2, 3: 3}
>>> foo("TOP", ["TIK", "PPPO", "OP"])
{3: 5}
>>> foo("FIND", ["VERYFAST", "OPINION", "SPENDING", "ODD"])
{4: 3, 6: 8}

C++に変換。mapに追加したりたどったりする方法がわからなくてかなり手間取った。

  for(int i=0; i<elementof(findpos); i++){
    can.insert(map<int, int>::value_type(findpos[i], 0));
  }

  for(map<int, int>::iterator it=can.begin();it != can.end(); it++){
    cout << (*it).first << endl;
  }

ほとんど書けたけどいまmap = newmapで悩んでいる。そのまま書いていいわけがないよな。うーん。

書き終わったけどうまく動かない。とりあえずPythonだったらprintしてチェックできるけどcout <<してもコンパイルエラーになるだけ。うーん。

template<class Iterator>
void map_print(const Iterator& begin, const Iterator& end){
  cout << "{";
  for(Iterator it=begin; it != end; it++){
    if(it != begin) cout << ", ";
    cout << (*it).first << ":" << (*it).second;
  }
  cout << "}" << endl;
}

int main() {
  typedef map<int, int> mii;
  mii d;
  d.insert(mii::value_type(1, 2));
  d.insert(mii::value_type(2, 3));
  d.insert(mii::value_type(3, 4));
  d[4] = 5;
  map_print(d.begin(), d.end());
}

とりあえず表示する関数を作ってみた。うー。もう１時間以上経っているぞ。このままでは実際の戦いでも１問も解けないかもしれない。焦り始めた。

        • -

あるmap Mに対して「キーxがない」というつもりで「!M[x]」とやったが、これはキーxでデフォルトの値を作ってしまう。あとこれ値が0だったと木とか問題だ。

template<typename _K, typename _V>
bool has_key(map<_K, _V> m, _K k){
  return (m.find(k) != m.end());
};

int main() {
  typedef map<int, int> mii;
  mii d;
  d[4] = 5;
  map_print(d.begin(), d.end());
  cout << has_key(d, 4) << endl;
  cout << has_key(d, 5) << endl;
}

おー、できた。だいぶわかってきた。

        • -

最終的にsubmit時に270点をゲットした。システムテストにかけてみよう。
う、failした…。919を返すべき所で924か…うーん、まだ何か見落としがあるのか…。もう解ける気がしないのでできたところまでのコードを貼って終わりにする。

vector<int> getpos(string s, char c){
  vector<int> result;
  size_t start = s.find(c);
  while(start != -1u){
    result.push_back(start);
    start = s.find(c, start + 1);
  }
  return result;
}

int placeWords(string matchString, vector <string> matchWords) {
  size_t N = elementof(matchWords);
  map<int, int> can;
  vector<int> findpos = getpos(matchWords[0], matchString[0]);
  if(findpos.empty()){
    return -1;
  }
  for(size_t i=0; i<elementof(findpos); i++){
    can.insert(map<int, int>::value_type(findpos[i], 0));
  }

  for(size_t i=1; i<N; i++){
    findpos = getpos(matchWords[i], matchString[i]);
    if(findpos.empty()) return -1;
    map<int, int> newcan;
    for(size_t pi=0; pi<findpos.size(); pi++){
      int p = findpos[pi];
      for(map<int, int>::iterator it=can.begin();it != can.end(); it++){
	int k = (*it).first;
	if(p <= k){
	  int diff = k - p;
	  int score = can[k] + diff;
	  if(!has_key(newcan, k) || newcan[k] > score){
	    newcan[k] = score;
	  }
	}else{
	  int diff = p - k;
	  int score = can[k] + diff * i;
	  if(!has_key(newcan, k) || newcan[k] > score){
	    newcan[p] = score;
	  }
	}
      }
    }
    can.clear();
    can = map<int, int>(newcan.begin(), newcan.end());
    newcan.clear();
  }

  int minvalue = 10000;
  for(map<int, int>::iterator it=can.begin(), end=can.end(); it != end; it++){
    if((*it).second < minvalue){
      minvalue = (*it).second;
    }
  }
  return minvalue;
}