TopCoder SRM 441 DIV 2

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

500は痛恨のキャストミス。なぜlong longにしなかったぁあああ

Problem 250 DifferentStrings

Problem Statement
If X and Y are two Strings of equal length N, then the difference between them is defined as the number of indices i where the i-th character of X and the i-th character of Y are different. For example, the difference between the words "ant" and "art" is 1.

You are given two Strings, A and B, where the length of A is less than or equal to the length of B. You can apply an arbitrary number of operations to A, where each operation is one of the following:

  • Choose a character c and add it to the beginning of A.
  • Choose a character c and add it to the end of A.

Apply the operations in such a way that A and B have the same length and the difference between them is as small as possible. Return this minimum possible difference.

http://www.topcoder.com/stat?c=problem_statement&pm=10376&rd=13749 
// s2の方が長い
int difNum(string s1, string s2, int buffer){
	int ret=0;
	for(int i=0 ; i<s1.length() ; i++){
		if(s1[i] != s2[i+buffer]) ret++;
	}
	return ret;
}

class DifferentStrings {
public:
  int minimize(string A, string B) {
    int result = 100;

	if(A.length() == B.length()){
		return difNum(A,B,0);
	}

	int n=100;
	for(int i=B.length()-A.length() ; i>=0 ; i--){
		n = difNum(A, B, i);
		if(n==0) return 0;
		else if(result>n) result = n;
	}

    return result;
  }
};

"Choose a character c and add it to the end of A."の一文を見逃していて時間を食ってしまった。

Problem 500 PaperAndPaintEasy

Problem Statement
Onise likes to play with paper and paint. He has a piece of paper with dimensions width x height. He does the following steps with the paper:
Fold the paper along the line x = xfold (the left side of the paper is folded over the right side).
Divide the paper vertically into cnt+1 equal sections. Then, cnt times, take the topmost section and fold it over the section below it.
Paint a rectangle with the lower-left corner at (x1, y1) and the upper-right corner at (x2, y2). Note that (0, 0) is now the lower-left corner of the paper in its current folded state, not its original state. The paint will seep through all the layers of the folded paper. See the image below for clarification.
Unfold the paper.
For example, let's say Onise has a piece of paper that is 5 x 6. He performs the described steps where xfold is 2, cnt is 2, and the coordinates of the painted rectangle's corners are (1, 1) and (3, 2). The following will happen (note that the paper starts out blue in the images and gets painted white):

You are given ints width and height, and ints xfold, cnt, x1, y1, x2 and y2. Return the total area of of the paper that is not covered in paint after Onise is done.

http://www.topcoder.com/stat?c=problem_statement&pm=10468&rd=13749 
ll ynum(int x1, int y1, int x2, int y2, int xfold, int width){
	ll pwidth = x2-x1;
	ll pheight = y2-y1;

	ll sum=0;

	ll x3 = x1+xfold;
	ll x4 = x2+xfold;

	ll x6 = x3-x1*2;
	ll x5 = x6-pwidth;

	if(x3 > width) x3=width;
	if(x4 > width) x4=width;
	if(x5 < 0) x5=0;
	if(x6 < 0) x6=0;

	sum = (x4-x3)+(x6-x5);
	return sum*pheight;
}

class PaperAndPaintEasy {
public:
  long long computeArea(int width, int height, int xfold, int cnt, int x1, int y1, int x2, int y2) {
    ll result;
	result = (ll)height*(ll)width - ynum(x1, y1, x2, y2, xfold, width)*(ll)(cnt+1);
	return result;
   }
};

すっげー時間がかかってしまった。1時間弱。
全てintで書いてしまっていたので、見事にSystem Testで落とされました。long longで渡されてるんだから気づけ俺。
次からは気をつけるようにすればいいんですよ・・・！

Problem 1000 PerfectPermutationHard

Problem Statement
A permutation A[0], A[1], ..., A[N-1] is a sequence containing each integer between 0 and N-1, inclusive, exactly once. Each permutation A of length N has a corresponding child array B of the same length, where B is defined as follows:

B[0] = 0
B[i] = A[B[i-1] ], for every i between 1 and N-1, inclusive.

A permutation is considered perfect if its child array is also a permutation.

Below are given all permutations for N=3 with their child arrays. Note that for two of these permutations ({1, 2, 0} and {2, 0, 1}) the child array is also a permutation, so these two permutations are perfect.

Permutation Child array
{0, 1, 2} {0, 0, 0}
{0, 2, 1} {0, 0, 0}
{1, 0, 2} {0, 1, 0}
{1, 2, 0} {0, 1, 2}
{2, 0, 1} {0, 2, 1}
{2, 1, 0} {0, 2, 0}

You are given a int[] P containing a permutation of length N. Find a perfect permutation Q of the same length such that the difference between P and Q is as small as possible. The difference between P and Q is the number of indices i for which P[i] and Q[i] are different. If there are several such permutations Q, return the one among them that has the lexicographically smallest child array.

http://www.topcoder.com/stat?c=problem_statement&pm=10469&rd=13749

無理ゲー