mayoko’s diary

プロコンとかいろいろ。

SRM 490 div1 med: QuickT9

解法

まず, t9 の各文字列の k 文字目までを作るのにかかるコストを計算します。
これには, t9 の各文字列 s について, s の k 文字目以下の番号(問題文の D というやつ) が一致しているやつを列挙し, それらの中で s.substr(0, k) が何番目に来るのかを求めれば良いです。

これにより, t9 から作ることの出来る文字列について, それを作るために必要な最小操作回数が得られます。

最小操作回数が得られたら, 後はダイクストラします。

d[i] = (i 文字目までを構成するのにかかる操作回数) として, グラフは以下のように構成できます。

i 文字目から何らかの文字列 p を付け加えた後, C を何回か行うことにより, 新しい文字列を作ることを考える。
word[i]+p という文字列から, 後ろの文字を削っていって, word.substr(0, j) と一致したら, 頂点 i から 頂点 j へ辺を追加します。

このような遷移が t9 を使ってできる遷移の全てなので, このグラフについてダイクストラすれば答えが得られます。

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

int number(char c) {
    if ('a' <= c && c <= 'c') return 2;
    if (c <= 'f') return 3;
    if (c <= 'i') return 4;
    if (c <= 'l') return 5;
    if (c <= 'o') return 6;
    if (c <= 's') return 7;
    if (c <= 'v') return 8;
    return 9;
}

vector<string> candString(const string s, const vector<string>& cand) {
    vector<string> ret;
    int len = s.size();
    for (string t : cand) {
        if (t.size() < s.size()) continue;
        string u = t.substr(0, s.size());
        bool ng = false;
        for (int i = 0; i < len; i++) {
            if (number(s[i]) != number(u[i])) {
                ng = true;
                break;
            }
        }
        if (!ng) ret.push_back(u);
    }
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
    return ret;
}


class QuickT9 {
public:
    int minimumPressings(vector <string> t9, string word) {
        vector<string> cand;
        for (string s : t9) {
            stringstream ss(s);
            string t;
            while (ss >> t) cand.push_back(t);
        }
        map<string, int> mp;
        for (string s : cand) {
            int len = s.size();
            for (int k = 1; k <= len; k++) {
                string t = s.substr(0, k);
                vector<string> cands = candString(t, cand);
                int plus = 0;
                for (; ; plus++) if (cands[plus] == t) break;
                if (mp.find(t) == mp.end()) mp[t] = k+plus+1;
                else mp[t] = min(mp[t], k+plus+1);
                t = s.substr(0, k-1);
                if (mp.find(t) == mp.end()) mp[t] = k+plus+1;
                else mp[t] = min(mp[t], k+plus+1);
            }
        }
        // dijkstra
        int n = word.size();
        vector<vector<edge> > G(n+1);
        for (int i = 0; i < n; i++) {
            for (auto p : mp) {
                string s = word.substr(0, i) + p.first;
                int cost = p.second;
                while ((int)s.size() > i) {
                    if (s == word.substr(0, s.size())) G[i].emplace_back(s.size(), cost);
                    cost++;
                    s.pop_back();
                }
            }
        }
        auto d = dijkstra(n+1, G, 0);
        ll ans = d[n];
        if (ans > 100000000) ans = -1;
        return (int)ans;
    }
};