Hatena::Grouptopcoder

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

 | 

2011-12-18

Single Round Match 527 22:28 Single Round Match 527 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 527 - nodchipのTopCoder日記 Single Round Match 527 - nodchipのTopCoder日記 のブックマークコメント

Easy 275 P8XGraphBuilder

  • 275・・・
  • 嫌な予感しかしない・・・
  • とりあえず読んでみる。
  • 溢れんばかりのDP
  • さてどうしたものか
  • とりあえずdp[ノード数]でいけるかどうか考えてみる
  • なんか色々無理っぽい
  • 次元を拡張してdp[ノード数][枝の数]的な感じで考えてみる
  • ・・・
  • まだなにか足りない
  • うむむ・・・
  • Easyってこんなに難しかったっけ?
  • とりあえずdp[使用するノード数][使用する枝の数][1つ当たりの枝に使う最大のノード数]=新しくノードを作った時のmaxスコア というへんちくりんなDPなら行けそうなことが分かった
  • 書いてみる
  • ・・・
  • 頭がこんがらがってきた
  • 新しいノードを作るところは別DP表にしよう
  • dp1[ノード数] と dp2[ノード数][枝の数][最大ノード数]
  • これ275のコードじゃないよね・・・
  • 絶対もっと簡単な方法があるはず
  • でもとりあえずこれで書く
  • 怖いのでassert入れまくり
  • ・・・
  • 書けたのでサンプル流しこんでみる
  • assertに引っかかりまくってるorz
  • とりあえず1つずつ潰していく
  • assert通った
  • 答えが合わない
  • rootのノードだけ別処理してみる
  • 通った
  • もう45分も使ってるorz
  • Passed System Test
const int nil = -1;
int dpOne[64];
// 使用可能ノード数, 残り何エントリ, 最大ノード数
int dpMulti[64][64][64];

class P8XGraphBuilder {
public:
	vector <int> scores;
	int f(int numberOfNodes) {
		int& r = dpOne[numberOfNodes];
		if (r != nil) {
			return r;
		}

		if (numberOfNodes == 1) {
			return scores[0];
		}

		r = 0;
		for (int numberOfEntries = 1; numberOfEntries < numberOfNodes; ++numberOfEntries) {
			r = max(r, f(numberOfNodes - 1, numberOfEntries, numberOfNodes - 1) + scores[numberOfEntries]);
		}
		return r;
	}
	int f(int numberOfNodes, int numberOfEntries, int maxNodes) {
		if (numberOfNodes == 0 && numberOfEntries == 0 && maxNodes == 0) {
			return 0;
		}

		assert(numberOfNodes >= maxNodes);
		assert(numberOfNodes > 0);

		int& r = dpMulti[numberOfNodes][numberOfEntries][maxNodes];
		if (r != nil) {
			return r;
		}

		if (numberOfNodes == 1) {
			assert(numberOfEntries == 1);
			assert(maxNodes == 1);
			return scores[0];
		}

		r = nil;
		for (int consume = 1; consume <= maxNodes; ++consume) {
			if (consume * numberOfEntries < numberOfNodes) {
				continue;
			}

			if (numberOfNodes - consume < numberOfEntries - 1) {
				continue;
			}

			int a = f(consume);
			assert(a != nil);
			int b = f(numberOfNodes - consume, numberOfEntries - 1, min(numberOfNodes - consume, consume));
			assert(a != nil);
			r = max(r, a + b);
		}
		return r;
	}
	int solve(vector <int> scores) {
		this->scores = scores;
		fill_n(dpOne, sizeof(dpOne) / sizeof(int), nil);
		fill_n((int*)dpMulti, sizeof(dpMulti) / sizeof(int), nil);

		int numberOfNodes = scores.size() + 1;
		int r = 0;
		for (int numberOfEntries = 1; numberOfEntries < numberOfNodes; ++numberOfEntries) {
			r = max(r, f(numberOfNodes - 1, numberOfEntries, numberOfNodes - 1) + scores[numberOfEntries - 1]);
		}

		return r;
	}
}

Middle 450 P8XMatrixRecovery

  • 残り20分しかないorz
  • なんかマッチングとか使いそうな気はする
  • ・・・
  • さっぱりわからんorz

以下はPracticeで通したコードです

class P8XMatrixRecovery {
public:
	// 最大流
	typedef vector<int> Array;
	typedef vector<Array> Matrix;
	int maxFlow(Matrix& capacity, int s, int t)
	{
		const int n = capacity.size();
		int result = 0;
		for (;;){
			vector<int> open;
			open.push_back(s);
			vector<int> prev(n, -1);
			while (!open.empty() && prev[t] == -1){
				const int from = open.back();
				open.pop_back();
				for (int to = 0; to < n; ++to){
					if (prev[to] >= 0 || !capacity[from][to]){
						continue;
					}
					prev[to] = from;
					open.push_back(to);
				}
			}
			if (prev[t] == -1){
				break;
			}
			vector<int> path;
			path.push_back(t);
			int flow = INT_MAX;
			while (path.back() != s){
				flow = min(flow, capacity[prev[path.back()]][path.back()]);
				path.push_back(prev[path.back()]);
			}
			for (int i = 0; i < path.size() - 1; ++i){
				capacity[path[i + 1]][path[i]] -= flow;
				capacity[path[i]][path[i + 1]] += flow;
			}
			result += flow;
		}
		return result;
	}

	bool ok(const string& lh, const string& rh) {
		REP(i, lh.size()) {
			if (lh[i] == '?' || rh[i] == '?') {
				continue;
			}
			if (lh[i] != rh[i]) {
				return 0;
			}
		}
		return 1;
	}

	bool ok(const vector<string>& rows, const vector<string>& columns) {
		const int C = columns.size();
		Matrix m(C * 2 + 2, Array(C * 2 + 2));
		REP(c, C) {
			m[C * 2][c] = 1;
			m[C + c][C * 2 + 1] = 1;
		}
		REP(left, C) {
			string s;
			REP(r, rows.size()) {
				s += rows[r][left];
			}

			REP(right, C) {
				m[left][C + right] = ok(s, columns[right]);
			}
		}

		return maxFlow(m, C * 2, C * 2 + 1) == C;
	}

	vector <string> solve(vector <string> rows, vector <string> columns) {
		vector <string> result;
		REP(r, rows.size()) {
			REP(c, rows[r].size()) {
				if (rows[r][c] != '?') {
					continue;
				}

				rows[r][c] = '0';
				if (!ok(rows, columns)) {
					rows[r][c] = '1';
				}
			}
		}
		return rows;
	}
}

Hard 1000

  • 読んでいません

Challenge Phase

  • 今回は撃墜ポイントが全く思いつかない
  • とりあえず450のアルゴリズムが分からないので人のコードを読んでみる
  • ・・・
  • 先頭から決めていけばいいのかorz

System Test

oxx 115.38pts 1746->1716 右肩下がりはまだまだ続きます

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