SRM579 Div1 Easy & Div2 Medium "UndoHistory"

問題

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

訳

ボブは奇妙なテキストエディタで何行かの文字を書く。そのエディタは３つの部品:（ウィンドウ・バッファ・アンドゥ）からできている。それらの詳細は以下の通りである。

ウィンドウ：複数の文字列で構成されている（表示されている）
          ：その文字列は既にあなたが書かれたものである
          ：始め、ウィンドウは空である

バッファ　：一つの文字列で構成されている
　　　　　：あなたが現在書いているものである
　　　　　：始め、バッファは空である。

アンドゥ　：複数の文字列で構成されている
　　　　　：過去のバッファの全ての状態を格納している
　　　　　：始め、空文字だけがある。

あなたは文字列の配列 lines が与えられる。ボブはlinesをウィンドウに表示させたいと思っている。（最終的に、linesの文字列の順番の通りに、ウィンドウにそれらの文字列を表示させたい）さらには、ボブはなるべく速く行いたいと思っている。彼は次のようなアクションができる。

・ボブはアルファベットの小文字をタイプすることができる。
　その文字はバッファへと追加される。
　その新しくできたバッファはアンドゥの新しい要素として追加される。
　（例えばバッファが"do"だとし、'g'をタイプしたとすると、
　バッファは"dog"となり、アンドゥへ"dog"が追加される）

・ボブはエンターを押すことができる。
　その時、ウィンドウに既に表示されている文字列の下に、
　現在のバッファの文字列が新しい行としてウィンドウに表示される。
　バッファに変更はない。（例えば、バッファが"dog"であり、
　ボブがエンターを押すと、"dog"がウィンドウに表示され、
　バッファは"dog"のままである。

・ボブはアンドゥにある好きな文字列をダブルクリックすることができる。
　その時、その文字列がバッファに格納される。
　この操作でアンドゥは変更されない。

ボブがウィンドウにlinesを表示させるのに必要な最小の押下数（キーボードとマウス）を返せ。

制約

1 <= linesの文字列数 <= 50
1 <= lines[i]の文字数 <= 50

考えた事

文字列 A を表示させ、また新しい文字列 B を表示させるには２つの方法がある。１つは、いまあるバッファをそのまま使う方法。これはダブルクリックしなくて済むが、BがAに0文字以上追加したようなものでなくてはならない。２つ目は新たに文字を打つ必要が最小で済むバッファをダブルクリックする方法。この２つの方法で少ない方を選んでいけばよい。

事後

後で気づいたが、３回もチャレンジされとる・・
たしかにソースコードから間違ってそうな雰囲気でてるわｗ

ソースコード

class UndoHistory {
public:

    int minPresses(vector <string> lines){
        int n = lines.size();

        int res = 0;
        lines.insert( lines.begin(), "" );
        for( int i = 1; i <= n; i++ ){
            bool ok = i != 0 && lines[i].length() >= lines[i-1].length();
            // 前の文字列の追加バージョンだ
            for( int j = 0; ok && j < lines[i-1].length(); j++ ){
                if( lines[i][j] != lines[i-1][j] ) ok = false;
            }
            int a = ok ? (lines[i].length() - lines[i-1].length()) : 10000;
            
            // もっとも合うバッファを探す+2
            int b = lines[i].length();
            for( int j = 0; j < i; j++ ){
                int t = 0;
                for( int k = 0; k < lines[j].length() && k < lines[i].length(); k++ ){
                    if( lines[i][k] != lines[j][k] ) break;
                    t++;
                }
                b = min( b, (int)lines[i].length() - t );
            }

            // ２つのうち小さいほうをとる
            res += min( a, b + 2 );

            // Enterを押す
            res++;
        }

        return res;
    }
};