Hatena::Grouptopcoder

cou929のTopCoder日記

2009-04-30

SRM419 div2(過去問)

23:28

Easy - ColumnDiagramPerimeter

グラフの周囲長を求める問題。特に難しいポイントはなし。

  int getPerimiter(vector <int> a)
  {
    int i;
    int ret = 0;

    ret = a.size() * 2;

    a.insert(a.begin(), 0);
    a.push_back(0);

    for (i=0; i<a.size()-1; i++) {
      ret += abs(a[i] - a[i+1]);
    }

    return ret;
  }

Medium - Undo

テキストエディタの一機能を実装している。2種類のコマンドがある。ひとつはtype s。文字sをテキストの末尾に追加するコマンド。もうひとつはundo n。時間nの時点まで処理を戻す。それぞれのコマンドには実行した時点の時間が記録されている。コマンドとそれを実行した時刻を入力とし、最終的なテキストを出力するという問題。

ポイントは再帰的に現れるundo命令をどう処理するかというところでしょう。僕がはじめにたてた戦略は、まずerase sという命令を導入。erase sはsをテキスト末尾から消去するという命令。そして、命令セットの先頭から走査し、undoだった場合は、undoが有効な時間だけ前に戻り、type sはerase sへ変換。逆にerase sはtype sへ変換していきます。こうすることで、最終的にはすべての命令がtypeとeraseのみになります。最後に命令を最初から順に処理し、出力のテキストを生成します。例えば、

commands = {"type a", "type b", "undo 2", "undo 2"}
time = {1, 2, 3, 4}

の場合、最終的な命令セットは、

{"type a", "type b", "erase a", "erase b", "type a", "type b", "erase b"}

となります。

しかし、この戦略だと実装がけっこう複雑になり、時間内には間に合いませんでした。

ほかの人のコードを見たところ、次の戦略をとっている人が多かったです。まず、命令セットを順に走査し、それぞれの時刻でのテキストの状態をvector <string>形式などで保存しておく。もしundo命令にさしかかったら、その時間だけ以前の状態へ戻すというものです。確かにこれならシンプルなので、実装も比較的容易です。

  string getText(vector <string> commands, vector <int> time)
  {
    int i;
    vector <string> V(100);
    string ret = "";

    for (i=0; i<commands.size(); i++)
      {
	if (commands[i][0] == 't')
	  {
	    V[i] = ret;
	    ret += commands[i][5];
	  }
	else
	  {
	    V[i] = ret;

	    int u;
	    sscanf(commands[i].c_str(), "undo %d", &u);

	    for (int j=i-1; j>=0; j--)
	      {
		if (time[i] - time[j] <= u)
		  {
		    ret = V[j];
		  }
		else
		  break;
	      }
	  }
      }

    return ret;
  }