TopCoder SRM 419 DIV 2

Problem	Check	Points
250	○	245.80
500	○	345.62
1000	-	-

今回は500は結構簡単だったという印象。
1000を結構ちゃんと考えられる時間があったのですが、「2つ以上のサイクルに含まれるような辺」をどのように判定すればいいのかわからず時間切れ。
はじめてUnion-find木使ってみました、便利だ。

Problem 250

問題

A column diagram is composed of n consecutive columns arranged in a horizontal row. Each column has a width of 1, and the base of each column is on the x-axis. The heights of the columns are given in the vector a, where a[i] is the height of the i-th column.
Return the perimeter of the given column diagram.

My code

class ColumnDiagramPerimeter {
public:
  int getPerimiter(vector <int> a) {
    int result=0;

	result += a.size()*2;
	for(int i=0 ; i<a.size()-1 ; i++){
		result += abs(a[i]-a[i+1]);
	}
	result += (a[0] + a[a.size()-1]);

    return result;
  }
};

Problem 500

問題

You are writing a simple text editor that supports only the following two commands:

• "type c" where c is a character: Append character c to the end of the current text.
• "undo t" where t is an integer: Undo all operations that were performed in the previous t seconds in reverse order.

All quotes are for clarity only. The text in the editor is initially empty.
For example, consider the following sequence of commands:

Second 1: type a
Second 2: type b
Second 3: type c
Second 5: undo 3

At the end of second 3, the text is "abc". At second 5, all commands performed in the previous 3 seconds are undone in reverse order. This means 'c' is removed, and then 'b' is removed. The text becomes just "a".
Note that "undo" commands can also be undone. For example:

Second 1: type a
Second 2: type b
Second 3: undo 2
Second 4: undo 2

After second 2, the text is "ab". After second 3, everything is undone, and the text becomes empty. At second 4, the previous "undo" is undone, so the text becomes "ab" again. Then, the "type b" is also undone and the text becomes just "a".
You are given a vector commands and a vector time. Each element of commands is a single command, and commands[i] is performed at time[i]. The commands are given in chronological order. Return the text after all the commands are executed.

My code

vector<string> split(const string& str, const string& delimiter) {
    // delimiter(2 文字以上も可) を空白に置換
    string item(str);    
    for(unsigned pos = item.find(delimiter); pos != string::npos; pos = item.find(delimiter, pos)) {
        item.replace(pos, delimiter.size(), " ");
    }
    // 分解
    stringstream buf(item);

    // 読み取り
    vector<string> result;
    while(buf >> item) {
        result.push_back(item);
    }

    return result;
}


class Undo {
public:
  string getText(vector <string> commands, vector <int> time) {
    string result = "";

	for(int i=time.size()-1 ; i>=0 ; i--){
		if(commands[i]=="") continue;
		vector<string> v = split(commands[i]," ,");

		if(v[0]=="type") continue;

		int t = atoi(v[1].c_str());
		
		for(int j=0 ; j<time.size() ; j++){
			if(time[i]-t <= time[j] && time[j] <= time[i]){
				commands[j]="";
			}
		}
	}


	for(int i=0 ; i<time.size() ; i++){
		if(commands[i]=="") continue;

		result += commands[i][5];
	}


    return result;
  }
};

Problem 1000

問題

A vertex cactus is a connected undirected graph such that each vertex belongs to at most one simple cycle. A simple cycle is a cycle that doesn't pass through any vertex more than once.

You are given an int n, the number of vertices in a graph G. The vertices are numbered from 1 to n. The edges in G are given in the vector edges. Concatenate the elements of edges to get a comma-separated list of integer pairs. The integers in each pair are separated by a space. The pair "i j" (quotes for clarity) means that there is an edge between vertices i and j. Return the number of connected components of G that are vertex cacti.