hotpepsiの練習帳

SRM 503 Div2

03:23

Easy (250) ToastXRaspberry 奇抜なトースト

文章がわかりづらい。

1. 一度に最大upper_limit層まで塗れる
2. layer_count層を塗るための最小の塗りの回数

ってこれだけ?

class ToastXRaspberry {
	public:
	int apply(int upper_limit, int layer_count) {
		return (layer_count + upper_limit - 1) / upper_limit;
	}
};

Medium (500) ToastXToast ナイスなトースト

境界条件の理解に時間がかかった。場合わけすると-1と1と2しかない。

焼いた種類のパンについて、必ずovertoastedとundertoastedが存在する、という文章を制約条件だと読んでいなかったため、システムテストに落ちた。汚かったので整理して書き直した。

#include <algorithm>
#include <vector>
using namespace std;
class ToastXToast {
	public:
	int bake(vector <int> undertoasted, vector <int> overtoasted) {
		sort(undertoasted.begin(), undertoasted.end());
		sort(overtoasted.begin(), overtoasted.end());
		if (undertoasted.size() < 1 || overtoasted.size() < 1) {
			return -1;
		}
		if (*undertoasted.rbegin() >= *overtoasted.rbegin() ) {
			return -1;
		}
		if (*undertoasted.begin() >= *overtoasted.begin() ) {
			return -1;
		}
		if (*undertoasted.rbegin() < *overtoasted.begin()) {
			return 1;
		}
		return 2;
	}
};

Hard (900) KingdomXCitiesandVillagesAnother 村を町につなぐ

孤立している村をなくせ。町または、町につながっている村とつなぐための道路を建設せよ。建設すべき道路の最小の合計値を求めよ。

残り15分くらいしかなく、テストのみ書いて終了。終了後、解いた人のソースを見て理解。

1. 村のうち、最小の長さで町に接続できる村を見つける。
2. 村と町を接続して、距離の合計値に加算する。
3. その村を村のリストから削除して、町のリストに追加する。

#include <math.h>
#include <list>
#include <vector>

using namespace std;

struct XY {
	int x;
	int y;
};

typedef vector<int> VI;
typedef list<XY> LXY;

class KingdomXCitiesandVillagesAnother {
	public:
	double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
		LXY cities, villages;
		VI::const_iterator x, y;
		for (x = cityX.begin(), y = cityY.begin(); x != cityX.end(); ++x, ++y) {
			XY city = {*x, *y};
			cities.push_back(city);
		}
		for (x = villageX.begin(), y = villageY.begin(); x != villageX.end(); ++x, ++y) {
			XY village = {*x, *y};
			villages.push_back(village);
		}
		double total = 0.0;
		while (villages.size() > 0) {
			double distance = 0.0;
			LXY::iterator it = findNearestVillage(cities, villages, distance);
			cities.push_back(*it);
			villages.erase(it);
			total += distance;
		}
		return total;
	}
	static LXY::iterator findNearestVillage(const LXY &cities, LXY &villages, double &distance) {
		LXY::iterator nearest = villages.end();
		LXY::iterator village;
		for (village = villages.begin(); village != villages.end(); ++village) {
			LXY::const_iterator city;
			for (city = cities.begin(); city != cities.end(); ++city) {
				double d = getDistance(*city, *village);
				if (nearest == villages.end() || d < distance) {
					nearest = village;
					distance = d;
				}
			}
		}
		return nearest;
	}
	static double getDistance(const XY &a, const XY &b) {
		double x = a.x - b.x;
		double y = a.y - b.y;
		return sqrt(x * x + y * y);
	}
};

結果

ox- 200.98+231.06*0

Easyのみシステムテストに通ってratingが932。Mediumが時間内にきちんと解けるようになりたい。

Hardは30分くらいで解くのはまだきつい感じ。