Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-10-28SRM419 DIV2

SRM419 DIV2 Level Two(500pt.)

| 22:02

http://www.topcoder.com/stat?c=problem_statement&pm=10054&rd=13510

『文字入力とアンドゥ操作のみが可能なテキストエディタがある。アンドゥは過去何秒間の操作を取り消すかを指定でき、入力だけでなくアンドゥ操作も取り消せる。実行するコマンドとその時間が与えられるとき、最終的にエディタへ入力された文字列を返せ。』

アンドゥと言えばスタックですが、このケースではアンドゥ自体もアンドゥによって取り消せるため適しません。時間軸を遡って処理をすることで、アンドゥされるコマンドははじめから解析しないように工夫しています。

// 458.40 pt.

public class Undo {
	public String getText(String[] commands, int[] time) {
		int undoTime = Integer.MAX_VALUE;
		final StringBuilder b = new StringBuilder();
		for (int i = time.length - 1; 0 <= i; --i) {
			if (undoTime <= time[i]) continue;

			final String[] command = commands[i].split(" ");
			if (command[0].equals("undo")) {
				undoTime = time[i] - Integer.parseInt(command[1]);
			} else {
				b.append(command[1]);
			}
		}
		return b.reverse().toString();
	}
}