TopCoder SRM 514 DIV2

Rating: 951(緑)→1026(緑)

やっとTopCoder登録直後のインチキレート(1031)に近付いてきた。その間1年。

250: MagicalGirlLevelOneDivTwo

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

class MagicalGirlLevelOneDivTwo {
private:
	inline int iabs(int x) {
		return x < 0 ? -x : x;
	}
public:
	double theMinDistance(int d, int x, int y) {
		int xm = iabs(x) - d, ym = iabs(y) - d;
		if (xm < 0) xm = 0;
		if (ym < 0) ym = 0;
		return sqrt(xm * xm + ym * ym);
	}
};

別に普通であるが、脳内では地味に混乱しながら書いたコードである事が伺える。

500: MagicalGirlLevelTwoDivTwo

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

class MagicalGirlLevelTwoDivTwo {
private:
	class Coord {
	public:
		int x, y;
		Coord(){return;}
		Coord(int x, int y) {
			this->x = x;
			this->y = y;
		}
	};
	class Validator {
	private:
		vector<vector<bool> > f;
		static const int width = 500;
	public:
		Validator() {
			f = vector<vector<bool> >(width * 2, vector<bool>(width * 2, false));
		}
		inline bool valid(int x, int y) {
			return -width < x && x < width && -width < y && y < width;
		}
		inline void fill(int x, int y) {
			f[x + width][y + width] = true;
		}
		inline bool filled(int x, int y) {
			if (!valid(x, y))
				return true;
			return f[x + width][y + width];
		}
	};
public:
	string isReachable(vector <int> jumpTypes, int x, int y) {
		queue<Coord> qu;
		qu.push(Coord(0, 0));
		Validator va;
		va.fill(0, 0);

		while(!qu.empty()) {
			Coord co = qu.front();
			qu.pop();
			if (co.x == x && co.y == y)
				return string("YES");
			for (int i = 0; i < jumpTypes.size(); ++i) {
				int n = jumpTypes[i];
				const int move[8][2] = {{n, 1}, {n, -1}, {-n, 1}, {-n, -1},
							{1, n}, {-1, n}, {1, -n}, {-1, -n}};
				for (int j = 0; j < 8; ++j) {
					int nx = co.x + move[j][0], ny = co.y + move[j][1];
					if (!va.filled(nx, ny)) {
						va.fill(nx, ny);
						qu.push(Coord(nx, ny));
					}
				}
			}
		}
		return string("NO");
	}
};

これもやはりかなり混乱しながら書いたコード。実際に提出した版にはさらにMagicalGirlLevelTwoDivTwo::Validator::dump()というメソッドがある。
というかDIV1ではこれの値域がでかい問題になっているという話を聞いたのだけれども、値域がでかい場合にはどう解けばいいのかイマイチ分かっていない。

1000: MagicalGirlLevelThreeDivTwo

オーダーを見積り間違えてひどいコードを書き間に合わず。
あとで考えなおしたい。