naoya_t@topcoder

SRM411 Div1 Easy: SentenceDecomposition

過去問, 練習 | 18:08 |

最初プライオリティキューとか駆使して探索していたが（※２つ目のコード。ちゃんと書かないと全テスト通過できないので、250点にしては難しめでは？と思ったけど）これはDPで書くと超簡単に解ける例。

DP、というか再帰とメモ化で解けるパターンを見つける練習が必要。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

string strsort(const string &str) {
  vector<char> buf(all(str));
  sort(all(buf));
  string sorted(all(buf));
  return sorted;
}

class SentenceDecomposition {
private:
  int score(string orig, string word) {
    if (strsort(orig) != strsort(word)) return -1;
    int d = orig.length();
    for (int i=d-1; i>=0; i--) if (orig[i] == word[i]) d--;
    return d;
  }
public:
  int len;
  string sent;
  vector<string> valids;
  vector<int> memo;

  int sub(int len) {
    if (len==0) return 0;
    if (memo[len] < INT_MAX) return memo[len];
    int min_score = INT_MAX;
    tr(valids,it) {
      int vl = it->length(); if (vl > len) continue;
      int subsc = sub(len-vl); if (subsc == INT_MAX) continue;
      int sc = score(*it,sent.substr(len-vl,vl)); if (sc == -1) continue;
      sc += subsc; if (sc < min_score) min_score = sc;
    }
    memo[len] = min(memo[len], min_score);
    return min_score;
  }

  int decompose(string sentence, vector<string> validWords) {
    sent = sentence; len = sentence.length();
    valids = validWords;
    memo.resize(len+1); fill(all(memo),INT_MAX);

    int topscore = sub(len);
    return (topscore == INT_MAX)? -1 : topscore;
  }
};

以下、最初に書いたコード。このコードで（何度か修正した末）システムテストも全て通るようになったが、TopCoderの統計情報を見たらこの問題はDPに分類されているので、書き直して上のコードになった。

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

bool greater_by_length(const string& s1, const string& s2 )
{
  return s1.length() > s2.length();
}
template <typename T> struct better : binary_function<T,T,bool> {
  bool operator()(const T& X, const T& Y) const{
    // at, score
    if (X.first >= Y.first) return X.second < Y.second;
    return false;
  }
};

string strsort(const string &str) {
  vector<char> buf(all(str));
  sort(all(buf));
  string sorted(all(buf));
  return sorted;
}

class SentenceDecomposition {
private:
  bool abc[26];
  bool usable(const string &str) {
    rep(i,str.length()) if (!abc[str[i]-'a']) return false;
    return true;
  }


  int score(string orig, string word) {
    int d = orig.length();
    for (int i=d-1; i>=0; i--) if (orig[i] == word[i]) d--;
    return d;
  }
public:
  int decompose(string sentence, vector<string> validWords) {
    int l=sentence.length();

    rep(i,26) abc[i] = false;
    rep(i,l) abc[sentence[i]-'a'] = true;

    set<string> s;
    tr(validWords,wt) if (usable(*wt)) s.insert(*wt);

    vector<string> valids(all(s));
    sort(all(valids),greater_by_length);

    int n=valids.size();
    vector<string> words(n);
    rep(i,n) {
      words[i] = strsort(valids[i]);
    }
    priority_queue<pair<int,int>, vector<pair<int,int> >, better<pair<int,int> > > pq;

    vector<int> said(l+1,INT_MAX);

    rep(i,n) {
      int wl = words[i].length();
      if (0+wl <= l) {
        string ss = sentence.substr(0,wl);
        if (strsort(ss) == words[i]) {
          int sc = score(valids[i],ss);
          if (sc < said[wl]) {
            pair<int,int> p = make_pair(wl,sc);
            pq.push(p);
            said[wl] = sc;
          }
        }
      }
    }

    int topscore = INT_MAX;

    while (!pq.empty()) {
      int at = pq.top().first, pt = pq.top().second;
      pq.pop();

      if (at == l) {
        topscore = min(topscore,pt);
        continue;
      }

      rep(i,n) {
        int wl = words[i].length();
        if (at+wl <= l) {
          string ss = sentence.substr(at,wl);
          if (strsort(ss) == words[i]) {
            int newscore = pt+score(valids[i],ss);
            if (newscore < topscore) {
              if (newscore < said[at+wl]) {
                pair<int,int> p = make_pair(at+wl,newscore);
                pq.push(p);
                said[at+wl] = newscore;
              }
            }
          }
        }
      }
    }

    return (topscore == INT_MAX)? -1 : topscore;
  }
};