TopCoder SRM 830 : Div1 Medium MorseCodeCorrector

面倒なだけで面白みを感じない問題。
https://community.topcoder.com/stat?c=problem_statement&pm=17596

問題

モールス信号に使われる2種類の記号(".","-")と、文字の境界を示す記号("|")を使い、メッセージを送ることを考える。
文字の境界は"|"で区切られ、単語の境界は"||"で区切られる。

今モールス信号と文字の境界を示す記号で構成された文字列Sが与えられる。
また、英大文字に対応するモールス信号の一覧が与えられる。

Sがモールス信号の書式にあったメッセージとなるようにしたい。
最小の文字書き換え数で済ませる場合、その文字列を答えよ。

解法

dp(n,b) := Sのprefix n文字を考える。単語の境界で終わっているかどうかを真偽値bで表すとき、そこまでモールス信号の文字または単語の境界として正しい場合に、書き換える最小文字数

とすると、dp(0,true)=0から始めてdp(|S|,false)が求める文字数となる。
dp(n,b)の状態から、文字A～Zまたは単語境界を置く場合を総当たりして状態遷移しよう。

最後にDPの復元をすれば、書き換え後の文字列も求められる。

string OK[]={
	".-|",
	"-...|",
	"-.-.|",
	"-..|",
	".|",
	"..-.|",
	"--.|",
	"....|",
	"..|",
	".---|",
	"-.-|",
	".-..|",
	"--|",
	"-.|",
	"---|",
	".--.|",
	"--.-|",
	".-.|",
	"...|",
	"-|",
	"..-|",
	"...-|",
	".--|",
	"-..-|",
	"-.--|",
	"--..|",
};

string from[5050][2];
int fromid[5050][2];
int cost[5050][2];



class MorseCodeCorrector {
	public:
	string fix(string message) {
		vector<string> cand[8];
		int i;
		message+="|";
		FOR(i,26) {
			cand[OK[i].size()].push_back(OK[i]);
		}
		int N=message.size();
		MINUS(fromid);
		FOR(i,N+1) cost[i][0]=cost[i][1]=1<<20;
		cost[0][0]=0;
		int j,k,id;
		
		FOR(i,N) FOR(id,2) if(cost[i][id]<1<<20) {
			
			if(id==1) {
				int co=cost[i][id]+(message[i]!='|');
				if(cost[i+1][0]>co) {
					cost[i+1][0]=co;
					from[i+1][0]="|";
					fromid[i+1][0]=1;
				}
			}
			
			for(j=1;i+j<=N&&j<=7;j++) {
				
				FORR(s,cand[j]) {
					int dif=0;
					FOR(k,j) dif+=message[i+k]!=s[k];
					if(cost[i+j][1]>cost[i][id]+dif) {
						cost[i+j][1]=cost[i][id]+dif;
						from[i+j][1]=s;
						fromid[i+j][1]=id;
					}
				}
			}
		}
		
		string ret;
		int cur=N;
		id=1;
		while(cur) {
			ret=from[cur][id]+ret;
			int ncur=cur-from[cur][id].size();
			int nid=fromid[cur][id];
			cur=ncur;
			id=nid;
		}
		ret.pop_back();
		return ret;
		
	}
}

まとめ

何がしたいんだろう…。