2014-05-10

■ TopCoder Single Round Match 620 Div 1 02:53

Easy 250 PairGame

(1,1)から全探索すると死ぬよなぁ・・・
問題をよく読みなおしてみる
上からやれば変化がひと通りに定まるのかな？
なら両方とも上からやって、後から共通部分を取ればいいか。
Passed System Test

class PairGame {
public:
	set<pair<int, int> > decompose(int x, int y) {
		set<pair<int, int> > decomposed;
		while (x >= 1 && y >= 1) {
			decomposed.insert(MP(x, y));
			if (x > y) {
				x -= y;
			}
			else {
				y -= x;
			}
		}
		return decomposed;
	}
	int maxSum(int a, int b, int c, int d) {
		set<pair<int, int> > A = decompose(a, b);
		set<pair<int, int> > B = decompose(c, d);

		int bestAnswer = -1;
		for (const auto& p : A) {
			if (B.count(p)) {
				MAX_UPDATE(bestAnswer, p.first + p.second);
			}
		}
		return bestAnswer;
	}
}

Medium 500 CandidatesSelection

試しに前からナイーブな探索+メモを書いてみる
・・・
終わるはずがない
後ろから探索とかできないかなぁ
最終的に欲しい配列を分割しつつverifyする感じ
とりあえずかけた
最大ケースはTLEしなさそう・・・
とりあえずsubmit
Failed System Test
[{"ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"}, {49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}] というテストケースで死んだっぽい。
これは無理っぽい。

Hard 800 PerfectSquare

ナイーブなDPは $O(2^(N * 2 + logN))$ とかになるのかな？
分からない。

Challenge Phase

500でナイーブなDPをしている人を探してみる
・・・
見つからなかったorz

System Test

oxx 229位 1864->1889 少しだけレーティングが上がりました。右肩下がりは止まったのでしょうか・・・。

追記 2014/05/11 10:07

500をPracticeで通しました。ただし想定解法ではありません。

class CandidatesSelection {
public:
	vector <string> score;
	vector<int> result;
	set<ll> memo;
	ll hash(const vector<vector<int> >& v) const {
		ll hash = -1;
		for (const auto& x : v) {
			for (int w : x) {
				hash *= 31;
				hash += w;
			}
			hash *= 31;
		}
		return hash;
	}
	bool dfs(const vector<vector<int> >& v) {
		ll h = hash(v);
		if (memo.count(h)) {
			return false;
		}
		memo.insert(h);

		if (clock() / double(CLOCKS_PER_SEC) > 1.8) {
			return false;
		}

		bool ok = true;
		for (const auto& part : v) {
			if (!is_sorted(ALL(part))) {
				ok = false;
				break;
			}
		}
		if (ok) {
			return true;
		}

		for (const auto& magnitudeRelation : score) {
			bool ok = true;
			vector<vector<int> > next;
			for (const auto& part : v) {
				for (int i = 0; i + 1 < part.size(); ++i) {
					if (magnitudeRelation[part[i]] > magnitudeRelation[part[i + 1]]) {
						ok = false;
						break;
					}
				}

				if (!ok) {
					break;
				}

				map<char, vector<int> > m;
				for (int x : part) {
					m[magnitudeRelation[x]].push_back(x);
				}

				for (const auto& bucket : m) {
					next.push_back(bucket.second);
				}
			}

			if (!ok) {
				continue;
			}

			if (dfs(next)) {
				return true;
			}
		}

		return false;
	}
	string possible(vector <string> score, vector <int> result) {
		this->score.clear();
		this->score.resize(score[0].size());
		for (const string& s : score) {
			REP(i, s.size()) {
				this->score[i] += s[i];
			}
		}
		this->result = result;
		memo.clear();

		vector<vector<int> > initial;
		initial.push_back(result);

		string res = dfs(initial) ? "Possible" : "Impossible";
		return res;
	}
}

■ AtCoder Beginner Contest #008 23:18

A - アルバム

引き算
Accepted

int main() {
	std::ios::sync_with_stdio(false);

	int S, T;
	cin >> S >> T;
	cout << T - S + 1 << endl;
}

B - 投票

mapに突っ込んでごにょごにょ
Accepted

int main() {
	std::ios::sync_with_stdio(false);
	int N;
	cin >> N;
	map<string, int> votes;
	REP(n, N) {
		string name;
		cin >> name;
		votes[name]++;
	}

	int bestVotes = 0;
	string bestName;
	for (const auto& v : votes) {
		if (bestVotes < v.second) {
			bestVotes = v.second;
			bestName = v.first;
		}
	}
	cout << bestName << endl;
}

C - コイン

とりあえず99点はnext_permutation()でいける
100点はどうやるんだろう・・・
確率と期待値と数え上げは本当に苦手・・・orz
これもしかして1枚ずつ独立に計算できるのかなぁ？
・・・
あるコインに着目して、そのコインより左にある枚数と、そのコインより左にある割り切れる数字を持ったコインの枚数とかで、掛け算しまくる感じ・・・？
うむむ・・・
多分大丈夫だと思う
Accepted

double C[128][128];
double BIKKURI[128];

int main() {
	std::ios::sync_with_stdio(false);

	REP(i, 128) {
		C[i][0] = 1.0;
	}
	for (int i = 1; i < 128; ++i) {
		for (int j = 1; j < 128; ++j) {
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
	}

	BIKKURI[0] = 1.0;
	for (int i = 1; i < 128; ++i) {
		BIKKURI[i] = BIKKURI[i - 1] * i;
	}

	int N;
	cin >> N;
	vector<int> coins;
	REP(n, N) {
		int coin;
		cin >> coin;
		coins.push_back(coin);
	}

	double sum = 0.0;
	REP(base, N) {
		int counter = 0;
		REP(other, N) {
			if (base == other) {
				continue;
			}

			if (coins[base] % coins[other] == 0) {
				++counter;
			}
		}

		for (int left = 0; left <= N - 1; ++left) {
			int right = N - 1 - left;
			for (int leftHit = 0; leftHit <= counter && leftHit <= left; ++leftHit) {
				if (leftHit % 2 != 0) {
					continue;
				}
				int rightHit = counter - leftHit;
				if (rightHit > right) {
					continue;
				}

				sum += C[left][leftHit] * C[right][rightHit] * BIKKURI[counter] * BIKKURI[N - counter - 1];
			}
		}
	}


	printf("%.20f\n", sum / BIKKURI[N]);
}

D - 金塊ゲーム

80点は全通り試すだけ・・・
99点->100点は座標圧縮かなぁ・・・
80点->99点が素で分からない。
諦めて苦肉の策で焼き鈍そう・・・orz
いい加減バカの一つ覚えから抜け出したいorz
80点のコードを焼きなましライブラリにつなげる
近傍状態は異なる2つの順序を入れ替えて作る
WA・・・
諦めきれないので焼きなまし温度パラメーターを変えて複数サブミットしてみる
温度パラメーター=0.040で99点出た！
ごめんなさい。本当にごめんなさい。

const int DX[] = { 0, 0, 1, -1 };
const int DY[] = { 1, -1, 0, 0 };

vector<pair<int, int> > initialMachines;
int N;

vector<int> space(const vector<int>& xs, int X) {
	vector<int> ret;
	ret.push_back(xs[0] - 1);
	ret.push_back(1);
	REP(i, xs.size() - 1) {
		ret.push_back(xs[i + 1] - xs[i] - 1);
		ret.push_back(1);
	}
	ret.push_back(X - xs.back());
	return ret;
}

int spacesX[64];
int spacesY[64];
ll calculate(const vector<pair<int, int> >& machines, int W, int H) {
	bool memo[64][64];
	CLEAR(memo);

	int counter = 0;
	for (const auto& machine : machines) {
		counter += spacesX[machine.first] * spacesY[machine.second];
		memo[machine.first][machine.second] = true;

		REP(dir, 4) {
			int x = machine.first + DX[dir];
			int y = machine.second + DY[dir];
			while (0 <= x && x < N * 2 + 1 && 0 <= y && y < N * 2 + 1 && !memo[x][y]) {
				counter += spacesX[x] * spacesY[y];
				memo[x][y] = true;
				x += DX[dir];
				y += DY[dir];
			}
		}
	}

	return counter;
}

#ifdef _MSC_VER
#include <Windows.h>
ll getTime() {
	return GetTickCount();
}
#else
#include <sys/time.h>
ll getTime() {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	ll result = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
	//cerr << result << endl;
	return result;
}
#endif

// http://www.jstatsoft.org/v08/i14/xorshift.pdf
unsigned int xor128() {     // 周期は 2^128-1
	static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	unsigned int t;
	t = (x ^ (x << 11)); x = y; y = z; z = w; return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

//TODO:状態を表す型/構造体を作成する
class STATE {
public:
	//TODO:コンストラクタに必要な引数を追加する
	explicit STATE();
	void next();
	void prev();
	double energy();
public:
	vector<pair<int, int> > machines;
	int src, dst;
};

class SimulatedAnnealing {
public:
	//TODO:コンストラクタに必要な引数を追加する
	SimulatedAnnealing();
	STATE run();
private:
	static const int TIME_LIMIT;
	double calculateProbability(double score, double scoreNeighbor, double temperature);
};

//TODO:コンストラクタに必要な引数を追加する
SimulatedAnnealing::SimulatedAnnealing() {
}

//TODO:計算時間をミリ秒単位で設定する
const int SimulatedAnnealing::TIME_LIMIT = 3900;

STATE SimulatedAnnealing::run() {
	const ll timeStart = getTime();
	const ll timeEnd = timeStart + TIME_LIMIT;
	STATE state;
	double energy = state.energy();
	STATE result = state;
	double minEnergy = energy;
	int counter = 0;
	ll timeCurrent;
	while ((timeCurrent = getTime()) < timeEnd){
		REP(loop, 100) {
			state.next();
			const double energyNeighbor = state.energy();
			const double random = xor128() * 0.00000000023283064365386962890625;
			const double probability = calculateProbability(energy, energyNeighbor, (double)(timeEnd - timeCurrent) / (double)(timeEnd - timeStart) + 1e-8);
			if (random < probability){
				//Accept
				if (minEnergy > energyNeighbor) {
#ifdef _MSC_VER
					fprintf(stderr, "minEnergy updated! %.5lf -> %.5lf\n", minEnergy, energyNeighbor);
#endif
					minEnergy = energyNeighbor;
					result = state;
				}
				//fprintf(stderr, "Accepted %.5lf -> %.5lf : minEnergy=%.5lf\n", energy, energyNeighbor, minEnergy);
				energy = energyNeighbor;
			}
			else {
				//Decline
				state.prev();
				//fprintf(stderr, "Declined\n");
			}
			++counter;
		}
	}
	fprintf(stderr, "counter:%d minEnergy:%.5lf\n", counter, minEnergy);
	return result;
}

double SimulatedAnnealing::calculateProbability(double energy, double energyNeighbor, double temperature) {
	if (energyNeighbor < energy) {
		return 1;
	}
	else {
		const double result = exp((energy - energyNeighbor) / (temperature + 1e-9) * 0.040);
		//fprintf(stderr, "%lf -> %lf * %lf = %lf\n", energy, energyNeighbor, temperature, result);
		return result;
	}
}

//TODO:初期状態を作る関数を記述する
STATE::STATE() {
	machines = initialMachines;
}

//TODO:遷移後の状態を作る関数を記述する
void STATE::next() {
	if (machines.size() == 1) {
		return;
	}

	src = xor128() % machines.size();
	do {
		dst = xor128() % machines.size();
	} while (src == dst);
	swap(machines[src], machines[dst]);
}

//TODO:遷移前の状態を作る関数を記述する
//     高々一つ前の状態までに戻れれば良い
void STATE::prev() {
	if (machines.size() == 1) {
		return;
	}

	swap(machines[src], machines[dst]);
}

//TODO:状態のエネルギーを計算する関数を記述する
//     状態はエネルギーの低い所に遷移する点に注意する
double STATE::energy() {
	return -calculate(machines, N * 2 + 1, N * 2 + 1);
}

int main() {
	std::ios::sync_with_stdio(false);

	ifstream cin("C:\\cygwin\\home\\nodchip\\procon\\abc008_4.2.in.txt");

	int W, H;
	cin >> W >> H;

	cin >> N;
	vector<pair<int, int> > machines;
	vector<int> xs;
	vector<int> ys;
	REP(n, N) {
		int x, y;
		cin >> x >> y;
		machines.push_back(MP(x, y));
		xs.push_back(x);
		ys.push_back(y);
	}

	sort(ALL(xs));
	sort(ALL(ys));

	vector<int> spacesX = space(xs, W);
	vector<int> spacesY = space(ys, H);

	REP(i, spacesX.size()) {
		::spacesX[i] = spacesX[i];
	}
	REP(i, spacesY.size()) {
		::spacesY[i] = spacesY[i];
	}

	for (auto& machine : machines) {
		machine.first = distance(xs.begin(), find(ALL(xs), machine.first)) * 2 + 1;
		machine.second = distance(ys.begin(), find(ALL(ys), machine.second)) * 2 + 1;
	}
	initialMachines = machines;

	STATE state = SimulatedAnnealing().run();
	cout << calculate(state.machines, N * 2 + 1, N * 2 + 1) << endl;

	//ll bestCounter = calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1);
	//bool updated = true;
	//while (updated) {
	//	updated = false;

	//	for (int n = 0; n + 1 < N; ++n) {
	//		swap(machines[n], machines[n + 1]);
	//		ll counter = calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1);
	//		if (bestCounter < counter) {
	//			bestCounter = counter;
	//			updated = true;
	//		}
	//		else {
	//			swap(machines[n], machines[n + 1]);
	//		}
	//	}
	//}

	//cout << bestCounter << endl;
}

結果

順位	ユーザ名	アルバム	投票	コイン	金塊ゲーム	得点 / Total
19	nodchip	100 00:36	100 02:24	100 (1) 104:39	99 (15) 87:48	399 (16)	184:39

どうにかこうにか1ページ目に入ることができました。Dは動的計画法だそうです。動的計画法は苦手です。

コメントを書く

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20140510

nodchipのTopCoder日記

2014-05-10

■ TopCoder Single Round Match 620 Div 1 02:53

Easy 250 PairGame

Medium 500 CandidatesSelection

Hard 800 PerfectSquare

Challenge Phase

System Test

追記 2014/05/11 10:07

■ AtCoder Beginner Contest #008 23:18

A - アルバム

B - 投票

C - コイン

D - 金塊ゲーム

結果