Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2010-06-19

TopCoderOpen 2010 Onlie Round 1 03:16 TopCoderOpen 2010 Onlie Round 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - TopCoderOpen 2010 Onlie Round 1 - nodchipのTopCoder日記 TopCoderOpen 2010 Onlie Round 1 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 EqualizeStrings

  • 貪欲法っぽくね?
  • aになるかmin(s, t)だよね?
  • sとtの間にaが来る条件はmin(s, y) <= 13とかそんな感じじゃね?

結果:Passed System Test

class EqualizeStrings {
public:
	string getEq(string s, string t) {
		string result;
		REP(i, s.size()) {
			int a = s[i];
			int b = t[i];
			if (abs(a - b) >= 13) {
				result += 'a';
			} else {
				result += min(a, b);
			}
		}
		return result;
	}
}

Middle 500 TwoRegisters

  • r<10^6だから幅優先探索したら探索空間10^12でTLEだよなぁ・・・
  • どうするんだろう・・・
  • 貪欲チックにやるんだろうなぁ多分
  • 問題文に書いてある表、これエラトステネスの篩っぽくね?
  • じゃあエラトステネスの篩だ。(<-えっ?)
  • 書いてみようか。

結果:Passed System Test

class TwoRegisters {
public:
	int gcd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}
	void create(const vector<int>& v, string& result) {
		char c;
		if (v.size() % 2 == 0) {
			c = 'Y';
		} else {
			c = 'X';
		}
		REP(i, v.size()) {
			result += string(v[i], c);
			c = (c == 'X' ? 'Y' : 'X');
		}
	}
	string minProg(int r) {
		string result(r + 1, '#');

		for (int first = r; first >= 1; --first) {
			if (gcd(r, first) != 1) {
				continue;
			}

			int a = r;
			int b = first;
			vector<int> v;
			int len = 0;
			bool go = true;
			while (b != 1) {
				len += a / b;
				if (len > result.size()) {
					go = false;
					break;
				}
				v.push_back(a / b);
				a %= b;
				swap(a, b);
			}
			if (!go) {
				continue;
			}
			v.push_back(a - 1);

			reverse(ALL(v));

			string s;
			create(v,s);

			if (s.size() < result.size() || s.size() == result.size() && s < result) {
				result = s;
			}
		}

		return result;
	}
}

Hard 1000 VacationTours

  • 探索するとTLEするよなぁ・・・
  • なんか上手いDPとかあるのかなぁ
  • 先頭からDPしてもなんかダメっぽいよなぁ
  • そもそもDPなのか?最小費用流ではダメなのか?
  • 良さそう
  • こんな感じにグラ含めばいけるんじゃね?
  • ・・・
  • なんか答えが合わない
  • もうだめぽorz

結果: Opened

以下はPracticeで遠たソースコードです。

// 最小費用流
// 負閉路にも対応している

// Spaghetti Source - グラフの基本要素
// http://www.prefield.com/algorithm/graph/graph.html
struct Edge {
	int src;
	int dst;
	int weight;
	int flow;
	Edge(int s, int d, int w, int f) : src(s), dst(d), weight(w), flow(f) {}
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
		e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef list<Edge> Edges;
typedef vector<Edges> Graph;

// Spaghetti Source - 単一始点最短路 (Bellman Ford)
// http://www.prefield.com/algorithm/graph/bellman_ford.html
static const int INF = INT_MAX / 2;
static const int NEGATIVE_CYCLE = INT_MIN / 2;
bool bellmanFord(const Graph& g, int s, vector<int>& dist, vector<int>& prev) {
	const int n = g.size();
	dist.assign(n, INF);
	dist[s] = 0;
	prev.assign(n, -2);
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (list<Edge>::const_iterator e = g[i].begin(); e != g[i].end(); ++e) {
				if (dist[e->dst] > dist[e->src] + e->weight) {
					dist[e->dst] = dist[e->src] + e->weight;
					prev[e->dst] = e->src;
					if (k == n - 1) {
						dist[e->dst] = NEGATIVE_CYCLE;
						return false;
					}
				}
			}
		}
	}
	return true;
}
vector<int> buildPath(const vector<int> &prev, int t) {
	vector<bool> memo(prev.size(), false);
	vector<int> path;
	for (int u = t; u >= 0 ; u = prev[u]) {
		if (memo[u]) {
			path.erase(path.begin(), find(path.begin(), path.end(), u));
			path.push_back(u);
			break;
		}

		memo[u] = true;
		path.push_back(u);
	}
	reverse(path.begin(), path.end());
	return path;
}

void updatePath(Graph& g, const vector<int>& path, int& restFlow, int& totalWeight, int& totalFlow)
{
	int bestFlow = restFlow;
	for (int i = 0; i < path.size() - 1; ++i) {
		// 一番コストの低い枝で更新する
		const int from = path[i];
		const int to = path[i + 1];
		int bestWeight = INT_MAX;
		int localBestFlow = 0;
		for (Edges::iterator it = g[from].begin(); it != g[from].end(); ++it) {
			if (it->src == from && it->dst == to && bestWeight > it->weight) {
				bestWeight = it->weight;
				localBestFlow = it->flow;
			}
		}

		if (bestFlow > localBestFlow) {
			bestFlow = localBestFlow;
		}
	}

	restFlow -= bestFlow;

	for (int i = 0; i < path.size() - 1; ++i) {
		const int from = path[i];
		const int to = path[i + 1];

		int bestWeight = INT_MAX;
		list<Edge>::iterator edge = g[from].end();
		for (list<Edge>::iterator it = g[from].begin(); it != g[from].end(); ++it) {
			if (it->src == from && it->dst == to && bestWeight > it->weight) {
				bestWeight = it->weight;
				edge = it;
			}
		}

		assert(edge != g[from].end());

		edge->flow -= bestFlow;

		if (edge->flow == 0) {
			g[from].erase(edge);
		}

		edge = g[to].end();
		for (list<Edge>::iterator it = g[to].begin(); it != g[to].end(); ++it) {
			if (it->src == to && it->dst == from && it->weight == -bestWeight) {
				edge = it;
				break;
			}
		}

		if (edge == g[to].end()) {
			g[to].push_back(Edge(to, from, -bestWeight, bestFlow));
		} else {
			edge->flow += bestFlow;
		}

		totalWeight += bestFlow * bestWeight;
	}

	if (path.front() != path.back()) {
		totalFlow += bestFlow;
	}
}

// <費用, フロー>
pair<int, int> minimumCostFlow(Graph &g, int s, int t, int restFlow) {
	int totalWeight = 0;
	int totalFlow = 0;
	const int n = g.size();
	for (;;) {
		//ステップ0:人工問題を解いて、需要供給量を満たすフローを求める
		//ステップ1:現在のフローに関する残余ネットワークを作る
		vector<int> label(n, -2);
		label[s] = -1;
		bool updated = true;
		while (updated) {
			updated = false;
			for (Graph::iterator it = g.begin(); it != g.end(); ++it) {
				for (Edges::iterator jt = it->begin(); jt != it->end(); ++jt) {
					if (label[jt->src] != -2 && label[jt->dst] == -2) {
						label[jt->dst] = jt->src;
						updated = true;
					}
				}
			}
		}

		if (label[t] == -2 || restFlow == 0) {
			//ステップ2:残余ネットワークに費用が負の閉路が存在しない⇒ 現在のフローは費用最小(終了)
			vector<int> dist;
			vector<int> prev;
			bellmanFord(g, s, dist, prev);
			if (find(dist.begin(), dist.end(), NEGATIVE_CYCLE) == dist.end()) {
				break;
			}

			//ステップ3:残余ネットワークの費用が負の閉路を求め、それを用いて現在のフローを更新する
			int cycleStart = (int)distance(dist.begin(), find(dist.begin(), dist.end(), NEGATIVE_CYCLE));
			vector<int> path = buildPath(prev, cycleStart);
			int tempRestFlow = INT_MAX;
			updatePath(g, path, tempRestFlow, totalWeight, totalFlow);

			//ステップ4:ステップ1へ戻る

		} else {
			vector<int> path;
			int current = t;
			while (current != -1) {
				path.push_back(current);
				current = label[current];
			}

			reverse(path.begin(), path.end());

			updatePath(g, path, restFlow, totalWeight, totalFlow);
		}
	}

	return make_pair(totalWeight, totalFlow);
}

class VacationTours {
public:
	int decode(char c) {
		if (isupper(c)) {
			return (int)c - 'A';
		} else if (islower(c)) {
			return (int)c - 'a' + 26;
		} else if (isdigit(c)) {
			return (int)c - '0' + 52;
		} else if (c == '+') {
			return 62;
		} else {
			return 63;
		}
	}
	int decode(char c, char d) {
		return decode(c) * 64 + decode(d);
	}
	int getIncome(vector <string> c, vector <string> d, int fee) {
		const int n = c.size();
		Graph g(2 * n);
		for (int sight = 1; sight < n; ++sight) {
			g[0].push_back(Edge(0, sight, decode(c[0][sight], d[0][sight]) - fee, 1));
			g[sight + n].push_back(Edge(sight + n, n, decode(c[sight][0], d[sight][0]), 1));
		}

		for (int i = 1; i < n; ++i) {
				g[i].push_back(Edge(i, i + n, 0, 1));
		}

		for (int from = 1; from < n; ++from) {
			for (int to = 1; to < n; ++to) {
				if (from == to) {
					continue;
				}
				g[from + n].push_back(Edge(from + n, to, decode(c[from][to], d[from][to]), 1));
			}
		}

		int sum = 0;
		int result = INT_MAX;
		for (int i = 0; i < n; ++i) {
			sum -= -minimumCostFlow(g, 0, n, 1).first;
			result = min(result, sum);
		}
		if (result < 0) {
			result = -result;
		} else {
			result = 0;
		}
		return result;
	}
}

Challenge Phase

  • 今回は通過が目標なので危ないことはしないようにしよう
  • 早速誰か落とされてる
  • 500だから全探索した人がいるんだろうなぁ
  • とりあえずなにもしないでおこう

System Test

o o x 166位 2128->2175 いい感じだったと思います。欲を言えば1000を解きたかったです。

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