読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 519 DIV2

Programming Algorithm TopCoder

Rating: 975(緑)→1014(緑)
600がいろいろとおかしい。おかしいのに通してしまったので恥ずかしい。

480.29 Point

250: WhichDay

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

class WhichDay {
public:
	string getDay(vector <string> notOnThisDay) {
		static const char *wd[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
		vector<string> weekdays(7);
		vector<bool> f(7, true);
		for (int i = 0; i < 7; ++i) {
			weekdays[i] = string(wd[i]);
		}
		for (int i = 0; i < notOnThisDay.size(); ++i) {
			for (int j = 0; j < weekdays.size(); ++j) {
				if (notOnThisDay[i] == weekdays[j]) {
					f[j] = false;
					break;
				}
			}
		}
		for (int i = 0; i < f.size(); ++i) {
			if (f[i]) {
				return weekdays[i];
			}
		}
		return string("");
	}
};

241.47 Point

600: ThreeTeleports

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

class ThreeTeleports {
private:
	class Telep {
	public:
		int fx, fy, tx, ty;
	};
public:
	int shortestDistance(int xMe, int yMe, int xHome, int yHome, vector <string> teleports) {

		long long int res = abs(xMe - xHome) + abs(yMe - yHome);
		sort(teleports.begin(), teleports.end());
		for (int i = 1, l = (1 << teleports.size()); i < l; ++i) {
			vector<string> curTeleps;
			for (int j = 0; j < teleports.size(); ++j) {
				if (i & (1 << j))
					curTeleps.push_back(teleports[j]);
			}
			do {
				vector<Telep> teleps;
				teleps.reserve(curTeleps.size());

				for (int i = 0; i < curTeleps.size(); ++i) {
					Telep t;
					stringstream ss(curTeleps[i]);
					ss>>t.fx>>t.fy>>t.tx>>t.ty;
					teleps.push_back(t);
				}

				for (int j = 0, l = (1 << teleps.size()); j < l; ++j) {
					vector<Telep> ct = teleps;
					for (int k = 0; k < teleps.size(); ++k) {
						if (j & (1 << k)) {
							swap(ct[k].fx, ct[k].tx); 
							swap(ct[k].fy, ct[k].ty); 
						}
					}
					long long int cur = 0;
					cur += abs(xMe - ct.front().fx) + abs(yMe - ct.front().fy) + 10;
					for (int k = 1; k < ct.size(); ++k) {
						cur += abs(ct[k - 1].tx - ct[k].fx) + abs(ct[k - 1].ty - ct[k].fy) + 10;
					}
					cur += abs(xHome - ct.back().tx) + abs(yHome - ct.back().ty);
					res = min(res, cur);
				}
			} while(next_permutation(curTeleps.begin(), curTeleps.end()));
		}
		return (int)res;
	}
};

いや、このコードはおかしいだろ…
僕は何の為にアルゴリズムとかを学習してきたんですか!と言いたくなるコード。
しかも通るのでタチが悪い。

238.82 Point

900: BinaryCards

問題文を読み終えたらあと10秒だった。
終わったあとで一応書いた。が一度落とした。なんてことを…

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

class BinaryCards {
public:
	long long largestNumber(long long A, long long B) {
		if (A == B)
			return B;
		for (int i = 62; 0 <= i; --i) {
			if (!(A & (1LL << i)) && (B & (1LL <<i))) {
				return B | ((1LL << i) - 1);
			}
		}
		return 0;

	}
};