Hatena::Grouptopcoder

peryaudoのTopCoder日記

 | 

2013-09-24

RelativePath

| 00:27

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>

using namespace std;

class RelativePath {
private:
	vector<string> separate(string path) {
		vector<string> res;
		for (int i = 0; i < path.size(); ++i) {
			if (path[i] == '/') {
				res.push_back("");
			} else {
				res.back() += path[i];
			}
		}
		if (res.size() == 1 && res[0] == "") {
			return vector<string>();
		}
		return res;
	}
	int getCommonLength(vector<string>& path, vector<string>& curdir) {
		for (int i = 0; i < min(path.size(), curdir.size()); ++i) {
			if (path[i] != curdir[i])
				return i;
		}
		return min(path.size(), curdir.size()); 
	}
public:
	string makeRelative(string path, string currentDir) {
		vector<string> pathSep = separate(path);
		vector<string> curDirSep = separate(currentDir);

		int commonLength = getCommonLength(pathSep, curDirSep);
		int backDepth = curDirSep.size() - commonLength;

		string res;
		for (int i = 0; i < backDepth; ++i) {
			res += "../";
		}

		for (int i = commonLength; i < pathSep.size(); ++i) {
			res += pathSep[i];
			if (i != pathSep.size() - 1)
				res += "/";
		}

		return res;
	}
};

一発

RevealTriangle

| 00:05

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>

using namespace std;

class RevealTriangle {
public:
	vector<string> calcTriangle(vector<string> qmt) {
		bool solved = false;
		while (solved == false) {
			solved = true;

			for (int i = qmt.size() - 2; 0 <= i; --i) {
			for (int j = qmt[i].size() - 1; 0 <= j; --j) {
				if (qmt[i][j] != '?') continue;
				if (j != qmt[i].size() - 1 && qmt[i + 1][j] != '?' && qmt[i][j + 1] != '?') {
					qmt[i][j] = ((qmt[i + 1][j] - '0') - (qmt[i][j + 1] - '0') + 10) % 10 + '0';
				} else if (j != 0 && qmt[i][j - 1] != '?' && qmt[i + 1][j - 1] != '?') {
					qmt[i][j] = ((qmt[i + 1][j - 1] - '0') - (qmt[i][j - 1] - '0') + 10) % 10 + '0';
				} else if (i != 0 && qmt[i - 1][j] != '?' && qmt[i - 1][j + 1] != '?') {
					qmt[i][j] = (qmt[i - 1][j] + qmt[i - 1][j + 1]) % 10 + '0';
				} else {
					solved = false;
				}
			}
			}
		}

		return qmt;
	}
};

一発

TheLuckyNumbers

| 23:37

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>

using namespace std;

class TheLuckyNumbers {
public:
	// count lucky numbers between 0 and x
	int getTop(int x) {
		while (x >= 10) {
			x /= 10;
		}
		return x;
	}

	int getDigit(int x) {
		int res = 0;
		if (x == 0) {
			res = 1;
		} else {
			while (x > 0) {
				res++;
				x /= 10;
			}
		}
		return res;
	}

	int removeTop(int x) {
		int removed = 1;
		for (int i = 0, iEnd = getDigit(x) - 1; i < iEnd; ++i) {
			removed *= 10;
		}
		return x - getTop(x) * removed;
	}

	bool isLucky(int x) {
		return x == 4 || x == 7;
	}

	int f(int x, int prevTop = 0) {
		if (x < 10) {
			if (x < 4) return 0;
			if (x < 7) return 1;
			return 2;
		}
		const int top = getTop(x);

		int res = 0;
		for (int cur = 0; cur <= top; ++cur) {
			bool lucky = isLucky(cur);
			const bool curEqTop = (cur == top);
			int prm = 1;
			for (int i = 0, iEnd = getDigit(x) - 1; i < iEnd; ++i) {
				prm *= 10;
			}
			prm--;

			int topRemoved = removeTop(x);

			if (cur == 0 && prevTop == 0) lucky = true;
			if (lucky && !curEqTop) {
				res += f(prm, cur);
			} else if (lucky && curEqTop) {
				res += f(topRemoved, cur);
			}
		}
		return res;
	}

	int count(int a, int b) {
		return f(b) - f(a - 1);
	}
};

いくらなんでも誤読が多すぎる。一発。

RandomSort

| 22:23

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <map>

using namespace std;

class RandomSort {
public:
	class Solver {
	public:
		vector<int> init;

		map<vector<int>, double> memo;
		set<vector<int> > visited;

		Solver(vector<int>& permutation) : init(permutation) {}

		bool sorted(vector<int>& perm) {
			for (int i = 0; i < perm.size(); ++i) {
				if (i + 1 != perm[i]) return false;
			}
			return true;
		}

		double solve(vector<int> perm) {
			if (memo.count(perm)) {
				return memo[perm];
			}

			if (sorted(perm)) {
				return memo[perm] = 0.0;
			}

			int cands = 0;
			for (int i = 0; i < perm.size(); ++i) {
			for (int j = i + 1; j < perm.size(); ++j) {
				if (perm[i] > perm[j])
					++cands;
			}
			}

			const double next = 1.0 / (double)(cands);

			double res = 0.0;

			for (int i = 0; i < perm.size(); ++i) {
			for (int j = i + 1; j < perm.size(); ++j) {
				if (perm[i] < perm[j]) continue;
				swap(perm[i], perm[j]);
				res += solve(perm) * next;
				swap(perm[i], perm[j]);
			}
			}

			res += 1.0;

			return memo[perm] = res;
		}

		double solve() {
			return solve(init);
		}

	};
	double getExpected(vector<int> permutation) {
		Solver solver(permutation);
		return solver.solve();
	}
};

TLEするような解き方をして1WA、メモ化で代入を忘れて1WA。

FIELDDiagrams

| 11:58

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>

using namespace std;

class FIELDDiagrams {
    public:
    long long countDiagrams(int fieldOrder) {
	vector<vector<long long> > dp(fieldOrder + 1, vector<long long>(fieldOrder + 1, 0));
	// dp[i][j] = rowsがi個で、a_1がj個の物の個数 (j <= i)
	dp[1][0] = 1, dp[1][1] = 1;
	for (int i = 2; i <= fieldOrder; ++i) {
	for (int j = 0; j <= i; ++j) {
		for (int k = 0;  k <= j; ++k) {
			dp[i][j] += dp[i - 1][k];
		}
	}
	}

	long long res = 0;
	for (int i = 0; i <= fieldOrder; ++i) {
		res += dp[fieldOrder][i];
	}

	res--;

	return res;
    }
};

最後に全くハコの無い状態を引く。

long long一度intにしてて落とした、つらい。

 |