Code Jam 2013 Round 1B Garbled Email

 前回復習したときに単純なDP解で解けたけど、上位陣の解答がおもしろそうだったのでrngさんのソースを見てみた。

あらかじめ辞書の単語でトライ木を作っておいて、（トライ木のどの節点にいるのか、間違った文字からの距離） -> 異なる文字の数をマップにいれて、それを毎回更新していくという処理をしている。

とりあえず一回写経して理解した後で、同じ解法を何も見ずに自分のスタイルで書いてみるという練習をしてみた。

最近きれいなソースを写経したり、どういうことを考えて実装されたソースなのかを考えたりするのが楽しくなってきた。これは良い練習方法かもしれない。

#include <algorithm>
#include <iostream>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

struct node {
    int next[26];
};

int ptr;

node trie[3000000];
bool goal[3000000];

void update(const string &s) {
    int cur = 0;
    REP (i, s.length()) {
        int c = s[i] - 'a';
        if (trie[cur].next[c] == -1)
            trie[cur].next[c] = ptr++;
        cur = trie[cur].next[c];
    }

    goal[cur] = true;
}

#include <fstream>
void init() {
    ptr = 1;
    memset(trie, -1, sizeof(trie));
    memset(goal, 0, sizeof(goal));

    fstream file("garbled_email_dictionary.txt");
    string s;
    int cnt = 0;
    while (file >> s) {
        update(s);
        ++cnt;
    }
    
    cerr << "dictionary size: " << cnt << endl;
}

void solve() {
    string s;
    cin >> s;
    int N = s.length();

    map<pair<int, int>, int> dp[4010];
    dp[0][make_pair(0, 4)] = 0;

    REP (i, N) {
        EACH (j, dp[i]) {
            REP (k, 26) {
                int st = j->first.first;
                int dist = j->first.second;
                int val = j->second;
                
                st = trie[st].next[k];
                if (st == -1)
                    continue;

                if (s[i] - 'a' == k) {
                    dist = min(dist+1, 4);
                } else {
                    if (dist < 4)
                        continue;
                    dist = 0;
                    ++val;
                }

                pair<int, int> p(st, dist);
                if (dp[i+1].find(p) == dp[i+1].end() || dp[i+1][p] > val)
                    dp[i+1][p] = val;
                if (goal[st]) {
                    p.first = 0;
                    if (dp[i+1].find(p) == dp[i+1].end() || dp[i+1][p] > val)
                        dp[i+1][p] = val;
                }
            }
        }
        dp[i].clear();
    }

    int ret = 1<<30;
    REP (i, 5) {
        pair<int, int> p(0, i);
        if (dp[N].find(p) != dp[N].end())
            ret = min(ret, dp[N][p]);
    }
    cout << ret << endl;
}

int main() {
    init();
    int T;
    cin >> T;
    REP (i, T) {
        printf("Case #%d: ", i+1);
        solve();
    }

    return 0;
}