TopCoder SRM 410 DIV 2

C/C++ TopCoder
Problem Check Points
250 ○ 159.99
500 × -
1000 - -

250 -> めんどくさかったし、これでいいのかすごく不安だった。
500 -> DIV2では正答率約5%の強敵。@uwitenpenさんのコードを1時間ぐらい眺めてようやく理解しました。自分の不甲斐なさを実感する毎日です。

TopCoder Statistics: SRM 410 Problem Set & Analysis

Problem 250 ContiguousCacheEasy

問題

In order to make their newest microcontroller as cheap as possible, the ACME Widget Company designed it with a very simple cache. The processor is connected to a slow memory system that contains n bytes, numbered 0 to n - 1. The cache holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1. When a program reads a byte, the cache controller executes the following algorithm:

  1. Find a new range of k bytes which contains the requested byte, such that the difference between the old and new base addresses is minimized. Note that if the requested byte was already in the cache, then the base address will not change.
  2. Update the cache to the new range by reading from the memory system any bytes that are in the new range but not the old range, and discarding any bytes that were in the old range but not the new range.
  3. Return the requested byte to the program.

To analyze the performance of a program, you wish to know how many bytes are read from the memory system. The numbers of the bytes that the program reads are given in addresses, in the order that they are read. When the program starts, the base address is 0.

My code
class ContiguousCacheEasy {
public:
  int bytesRead(int n, int k, vector <int> addresses) {
	  
	  int gcnt = 0;
	  int base = 0;
	  for(int i=0 ; i<addresses.size() ; i++){
		  int tmp = addresses[i];

		  int cnt;
		  if(base <= tmp && tmp < base+k) cnt = 0;
		  else if(tmp >= base+k ){
			  cnt = tmp-(base+k)+1;
			  base += cnt;
		  }
		  else{
			  cnt = base-tmp;
			  base -= cnt;
		  }
		  cout << "base -> " << base << ",cnt -> " << cnt << endl;
		  gcnt += min(cnt,k);

	  }
	  return gcnt;
  }
};

Problem 500 AddElectricalWires

問題

You are given an electrical circuit for a home, with a number of nodes possibly connected by wires. Any pair of nodes may be connected by at most one wire, and a node can't be connected to itself. Each node on the circuit is either an electrical outlet for the house or a connection to the main electrical grid. The String wires tells you the wires that are already in place; the xth character of the yth element is '1' (one) if nodes x and y have a wire between them, '0' (zero) otherwise. The int gridConnections lists the indices of the nodes that are connections to the main electrical grid.

You'd like to make the circuit safer and more redundant by adding as many extra wires to it as possible. The one complication is that no two main grid connections are currently wired together (directly or indirectly), and you must preserve this, or else disaster will result. Determine the maximum number of new wires you can add to the circuit.

My code
class AddElectricalWires {
public:
  int maxNewWires(vector <string> wires, vector <int> gridConnections) {
	  
	  int g[51][51];

	  int ed = 0;
	  for(int i=0 ; i<wires.size() ; i++){
		  for(int j=0 ; j<wires.size() ; j++){
			  if(wires[i][j]=='0') g[i][j] = 0;
			  else{
				  g[i][j] = 1;
				  ed++;
			  }
		  }
	  }

	  ed /= 2;


	  for(int k=0 ; k<wires.size() ; k++){
		  for(int i=0 ; i<wires.size() ; i++){
			  for(int j=0 ; j<wires.size() ; j++){
				  if(i==j) continue;
				  if(g[i][k]==1 && g[k][j]==1) g[i][j]=1;
			  }
		  }
	  }

	  int ret=0;
	  int mmax=0;
	  int coned=0;

	  // mmax -> gridConnectionsが属するクラスタの中で最大のクラスタの頂点数
	  for(int i=0 ; i<gridConnections.size() ; i++){
		  int c=1;
		  for(int j=0 ; j<wires.size() ; j++){
			  if(g[gridConnections[i]][j]==1) c++;
		  }

		  ret += c*(c-1)/2;
		  mmax = max(mmax,c);
		  coned += c;
	  }

	  // wires.size()-coned -> gridConnectionsが属していないクラスタ(?)の頂点数
	  int mm = mmax + (wires.size()-coned);

	  int a = mm*(mm-1)/2 + (ret-mmax*(mmax-1)/2);

	  return a-ed;
  }
};

Problem 1000 ClosestRegex

問題

A regular expression is a pattern describing how a particular string should be formed. For the purposes of this problem, a regular expression consists of atoms. Each atom is either a single lowercase letter (which matches exactly one of that letter), or a single lowercase letter followed by an asterisk ('*'), which matches zero or more of that letter. A string matches a regular expression if it can be partitioned into substrings which match the atoms of the regular expression in the same order. For example, the regular expression ab*c*b is matched by the strings ab, abb, acb and abbbcccb, but not by ba, accbb or babcb.

You have a string text which ought to match the regular expression regex. However, it may have been corrupted. Return the string S that satisfies the following conditions.

  1. S has the same number of characters as text.
  2. S matches regex.
  3. The number of positions in which S differs from text is minimal.
  4. S is lexicographically smallest amongst strings that satisfy the other conditions.

If there is no string that satisfies the above conditions, return the empty string.