TopCoder SRM 579 Div1 Easy UndoHistory

SRM579に参加。Mediumが450pt、これは解ける、と思ったらまたも凡ミス。
チャレンジまでの間に気づいてしまった…。
Easyは解けてレートは微増だが、この出来で微増できる今のレートも残念。

CFも２連続レートダウン（うち１つはやはり凡ミス）だし凡ミスをいかに減らしてEasyを確保するかが今後の課題だ。

ではEasyから復習。
http://community.topcoder.com/stat?c=problem_statement&pm=12523

問題

複数のアルファベット小文字からなる単語が与えられる。
これをテキストエディタに入力することを考える。
テキストエディタには特殊なバッファがあり、以下の様に動く。

• リターンを押すとバッファ中の単語がエディタに送られる(バッファの内容は残る)
• 小文字を入力するとその文字がバッファに追加される。また、このときUndo履歴にバッファの単語が追加される。
• Undo履歴中の単語をダブルクリックすると、その単語でバッファの内容が置き換わる。

初期状態でUndo履歴は空文字のみである。
指定された単語をエディタに打ちこむまでの最小キー・マウスボタン押下回数を答える。

解法

１つ目の単語は素直に文字列を入力してリターン。

２つ目以降は最短打鍵数を探す。このとき２つのアプローチがある。

• 1つ前の単語が、次に入力する単語のprefixなら、続けて打つ
• Undoリストに次に入力する単語のprefixがあれば、2マウス押下をしてそれを戻す

両者のうち打鍵数の少ない方を取ればよい。

また、各単語の入力後は、その各prefixをUndoリストに追加していく。
今回はsetで行った。

以下はSRM後に直したもの。
本番はもう単語長である50倍位時間のかかるコードを書いたが、問題なくpassした。

class UndoHistory {
	public:
	set<string> Vs;
	
	int minPresses(vector <string> lines) {
		int L=lines.size();
		
		Vs.clear();
		int i,j;
		int res=lines[0].size()+1;
		Vs.insert("");
		FOR(j,lines[0].size()+1) Vs.insert(lines[0].substr(0,j));
		
		for(i=1;i<L;i++) {
			int mi=9999;
			
			if(lines[i-1].size()<=lines[i].size() && lines[i-1]==lines[i].substr(0,lines[i-1].size()))
				mi=lines[i].size()-lines[i-1].size();
				
			FOR(j,lines[i].size()+1) {
				if(Vs.find(lines[i].substr(0,j))!=Vs.end()) mi=min(mi,2+(int)lines[i].size()-j);
			}
			res += mi+1;
			FOR(j,lines[i].size()+1) Vs.insert(lines[i].substr(0,j));
		}
		return res;
	}
};

まとめ

一部問題文がわかりにくいと取った参加者もいた様子。
幸い自分は問題の意図はつかめた。

本番はsubstrを使わず処理していたので、prefixを作ったり比較したりがとても面倒で時間を食った。
substrの引数順を覚えないとな。perlと一緒かな。