学步园

今天第一次参加了TopCoder SRM Match，SRM 582，开始前还蛮紧张的，因为是第一次参加，没有rating，只能参加division II，要求是要在80分钟内完成三个难度梯度的题目，分值分别是250, 500, 1000。250分的题目相当简单，5、6分钟就搞定了，提交后分数还好，有230多分，心情稍稍放松，之后打开500分值的题目，发现TopCoder的题目描述都挺有意思的，一个枯燥算法问题包装在一个有趣的背景下。看完题目觉得有点难，没有马上想到解决办法，然后就有点急了，觉得脑子开始有点混乱，为了平静下来，先把最简单的返回-1的情况写了。之后有了思路，码代码呀码代码，发现做这种算法比赛，熟悉C++的标准真是好处多多，以前写程序不知道用STL，不知道还有#include
<algorithm>这样的的好东西，使用链表、栈这样数据结构都是用以前自己实现的来搞，排序、求最大值之类算法都是手写，现在使用STL和C++提供标准标准值是爽。程序完成之后编译没问题，测试，结果悲剧了，4个测试用例前3个能过，第4个就不对了，纠结啊，然后一直检查算法是不是出问题了，是不是哪里粗心写错了，搞了半天，还是有问题，搞到比赛结束，程序还是不行，然后就这样把错的就这样提交了，最后System Testing 这题时得了0分。首次比赛就这样华丽丽的跪了，1000分的题目都没有来得及看，还有在coding
phase结束之后的challenge phase中因为challenge失败被扣了25分，悲剧！

比赛结束后rating居然到了948，也不知道是怎么评分的，之后继续调试500分的程序，终于找到问题了，在这个 while (magicalGirlStrength[i] < enemyStrength[j]) 循环条件中没有检查j，正确的应该是while (j >= 0 && magicalGirlStrength[i] < enemyStrength[j])，就这个问题导致程序崩溃，调试了将近一个小时了，无比坑！

下面是比赛题目：

Overview

Level One  SemiPerfectSquare
Level Two  SpaceWarDiv2
Level Three  ColorTheCells

我的代码：

Level One:

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

class SemiPerfectSquare
{
public:
	string check(int N);
};



string SemiPerfectSquare::check(int N)
{
	int sq = (int)sqrt((double)N);

	for (int i = 0; i <= sq; i++) {
		for (int j = 0; j < i; j++) {
			if (j * i * i == N) {
				return "Yes";
			}
		}
	}

	return "No";
}

Level Two:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int F[50];

class SpaceWarDiv2
{
public:
	int minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector <int> enemyCount);
};

int SpaceWarDiv2::minimalFatigue(vector<int> magicalGirlStrength, vector<int> enemyStrength, vector<int> enemyCount)
{
	int maxMS, maxES;
	int i, j;
	maxMS = *max_element(magicalGirlStrength.begin(), magicalGirlStrength.end());
	maxES = *max_element(enemyStrength.begin(), enemyStrength.end());
	if (maxMS < maxES) {
		return -1;
	}

	for (i = 0; i < 50; i++) {
		F[i] = 0;
	}

	sort(magicalGirlStrength.begin(), magicalGirlStrength.end());

	for (i = 0; i < enemyStrength.size()-1; i++) {
		for (j = i+1; j < enemyStrength.size(); j++) {
			if (enemyStrength[i] > enemyStrength[j]) {
				swap(enemyStrength[i], enemyStrength[j]);
				swap(enemyCount[i], enemyCount[j]);
			}
		}
	}
	while (!enemyCount.empty()) {
		for (i = 0; i < magicalGirlStrength.size(); i++) {
			j = enemyStrength.size() - 1;
			while (j >= 0 && magicalGirlStrength[i] < enemyStrength[j]) {
				--j;
			}

			if (j >= 0) {
				++F[i];
				--enemyCount[j];
				if (0 == enemyCount[j]) {
					enemyCount.erase(enemyCount.begin() + j);
					enemyStrength.erase(enemyStrength.begin() + j);
				}
			}
		}
	}


	return *max_element(F, F + magicalGirlStrength.size());
}