TopCoder SRM 579, Division 1, Level 1 ( Division 2, Level 2 ) : UndoHistory

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12523&rd=15499

概要

特殊なテキストエディタを使っていくつかの文字列を入力する。
実際に出力される内容は Results Window の内容である。

入力した文字列はバッファに入り、Enter キーの押下によりバッファの内容が Results Window に送られる。
このとき、バッファの内容はクリアされない。

また、Undo History という領域に、これまでバッファに存在したことのあるすべての文字列が蓄えられている。
初めは空文列のみが Undo History にある。
クリックを二回することで、バッファの内容を Undo History 内の任意の文字列にすることができる。

入力したい文字列の情報が与えられる。
タイプ数が最小になるようにして入力したときのタイプ数を求めよ。

解法

一行目は必ず全部打ち込んで Enter キーを押下する必要があります。
二行目以降は、以下の三つの選択肢があります。

• 二回クリックして空文字列を呼び出し、全部打つ
• バッファに残っている文字をそのまま利用して、残りの文字を入力する
• Undo History から入力したい文字列の最長の prefix を呼び出して、残りを入力する

どれを選んでも次に持ち越されるバッファの内容は変わらないので、最もタイプ数が少なくなるものを選べばよいです。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class UndoHistory
{
public:
	int minPresses( vector <string> lines )
	{
		string buffer;
		vector<string> history;

		int res = lines[0].size() + 1;

		REP( i, 1, lines.size() )
		{
			int need = 2 + lines[i].size();
			if ( lines[i].find( lines[ i - 1 ] ) == 0 ) // buffer が prefix
			{
				need = min<int>( need, lines[i].size() - lines[ i - 1 ].size() );
			}
			REP( j, 0, i )
			{
				REP( k, 0, min( lines[i].size(), lines[j].size() ) )
				{
					if ( lines[i].substr( 0, k + 1 ) == lines[j].substr( 0, k + 1 ) )
					{
						need = min<int>( need, 2 + lines[i].size() - k - 1 );
					}
				}
			}
			res += need + 1;
		}

		return res;
	}