Hatena::Grouptopcoder

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

 | 

2009-12-19

UVa Online Judge A Bangladeshi Contest 00:43 UVa Online Judge A Bangladeshi Contest - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - UVa Online Judge A Bangladeshi Contest - nodchipのTopCoder日記 UVa Online Judge A Bangladeshi Contest - nodchipのTopCoder日記 のブックマークコメント

UVa Online Judge A Bangladeshi Contestの参加記録です。

Problem A: Airports

N個の街と、街同士を道路で繋いだ時のコストが与えられる。街にはコストAで空港を設置することができる。道路でつながれた街は自由に行き来することができる。すべての街から空港のある街に行けるようにするために必要なコストの最小値を求めよ。

  • クラスカル・・・だよなぁ
  • 一本繋ぐ毎にコストの更新チェックだよなぁ。
  • 一問目からクラスカルかぁ・・・。レベル高いなぁ・・・。
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

typedef int Weight;
struct Edge {
	int src, dst;
	Weight weight;
	Edge(int src, int dst, Weight weight) :
	src(src), dst(dst), weight(weight) { }
};
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 vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

int N, M, A;
int X, Y;

pair<Weight, Edges> minimumSpanningForest(const Graph &g) {
	int n = g.size();
	UnionFind uf(n);
	priority_queue<Edge> Q;
	REP(u, n){
		for (Edges::const_iterator e = g[u].begin(); e != g[u].end(); ++e) {
			if (u < e->dst) Q.push(*e);
		}
	}

	int y = N;
	Weight total = 0;
	Edges F;
	while (F.size() < n-1 && !Q.empty()) {
		Edge e = Q.top(); Q.pop();
		if (uf.unionSet(e.src, e.dst)) {
			F.push_back(e);
			total += e.weight;

			--y;
			const int x = total + A * y;
			if (X > x) {
				X = x;
				Y = y;
			}
		}
	}
	return pair<Weight, Edges>(total, F);
}

int main()
{
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; ++t) {
		scanf("%d%d%d", &N, &M, &A);
		X = N * A;
		Y = N;

		Graph g(N + 1);

		for (int i = 0; i < M; ++i) {
			int x, y, c;
			scanf("%d%d%d", &x, &y, &c);
			g[x].push_back(Edge(x, y, c));
			g[y].push_back(Edge(y, x, c));
		}

		minimumSpanningForest(g);

		printf("Case #%d: %d %d\n", t, X, Y);
	}
}

Problem B: Big Number of Teams will Solve This

二つの文字列が与えられる。完全に同じならYes、一つ目の文字列からスペースを取り除いて二つ目になるならOutput Format Error、それ以外はWrong Answerと出力せよ。

  • やるだけゲー
  • 昔似たような問題やったなぁ
int main()
{
	int t;
	cin >> t;
	string line;
	getline(cin, line);
	for (int i = 1; i <= t; ++i) {
		string a, b;
		getline(cin, a);
		getline(cin, b);
		cout << "Case " << i << ": ";
		if (a == b) {
			cout << "Yes" << endl;
			continue;
		}
		a.erase(remove(a.begin(), a.end(), ' '), a.end());
		if (a == b) {
			cout << "Output Format Error" << endl;
		} else {
			cout << "Wrong Answer" << endl;
		}
	}
}

Problem C: Corner the Queens

チェス盤を使った二人ゲームを行う。クイーンを何処かに置き、順番に動かしていく。動かせるのは左方向、左下方向、下方向の三方向、(0,0)に移動できたプレイヤーの勝ち。チェス盤の区画が与えられたとき、先攻が何割のマスで勝つことが出来るか分数で求めよ。

  • 出ました苦手なゲーム木探索orz
  • とりあえず考えてみましょうか・・・
  • ゲーム木探索の基本は、次が全て勝ちなら負け、次にひとつでも負けがあれば勝ち、だったはず
  • とりあえず手元で書いてみる
  • 端っこと斜めは全部勝ち、残りは市松模様になった
  • コード書いた。サブミット。Wrong Answer・・・orz
  • 手元のメモを見直してみる
  • なんかメモが間違っている気がする
  • 改めて考えてみる
  • 市松模様じゃなくね?
  • 冷静に考え直してみる
  • なんか不規則な斜め方向の線が出た
  • Windowsのペイントでポチポチ描いてみる
  • 規則性が分からない
  • でもこれくらいの数なら全探索できるんじゃね?
  • 書いてみた 時間計算量大丈夫そう submit 勝利!
ll gcd(ll a, ll b) {
  return b != 0 ? gcd(b, a % b) : a;
}

int f(const vector<int>& xs, const vector<int>& ys, int x1, int y1, int x2, int y2)
{
	const int xBegin = (int)distance(xs.begin(), lower_bound(xs.begin(), xs.end(), x1));
	const int xEnd = (int)distance(xs.begin(), lower_bound(xs.begin(), xs.end(), x2));
	const int yBegin = (int)distance(ys.begin(), lower_bound(ys.begin(), ys.end(), y1));
	const int yEnd = (int)distance(ys.begin(), lower_bound(ys.begin(), ys.end(), y2));
	const int begin = max(xBegin, yBegin);
	const int end = min(xEnd, yEnd);
	return max(end - begin, 0);
}

int main()
{
	static bool used[1024 * 1024];
	memset(used, 0, sizeof(used));
	vector<int> xs;
	vector<int> ys;
	xs.push_back(2);
	ys.push_back(1);
	used[1] = true;
	used[2] = true;
	int x = 3;
	for (int y = 1; y <= 1000000 && x <= 1000000; ++y) {
		if (!(used[x] || used[y])) {
			used[x] = true;
			used[y] = true;
			xs.push_back(x);
			ys.push_back(y);
			++x;
		}
		++x;
	}

	int T;
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		ll x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		++x2;
		++y2;
		ll d = (x2 - x1) * (y2 - y1);
		ll n = d;
		n -= f(xs, ys, x1, y1, x2, y2);
		n -= f(xs, ys, y1, x1, y2, x2);

		const ll g = gcd(n, d);
		n /= g;
		d /= g;
		cout << "Board " << t << ": " << n << " / " << d << endl;
	}
}

Problem D: Debugging RAM

変数名と各変数名のビット数、メモリの状態が与えられる。各変数の値を求めよ。

  • やるだけゲー・・・だよなぁ
  • Wrong Answer・・・、なぜ?
  • 複数ケースに対応してなかった!なんという初歩的なミス!
  • submit Accepted orz
int main()
{
	for (int b, v; cin >> b >> v;) {
		string dummy;
		getline(cin, dummy);

		map<string, int> names;
		vector<int> sizes;
		for (int i = 0; i < v; ++i) {
			string line;
			getline(cin, line);
			string name;
			int size;
			if (line[0] == ' ') {
				istringstream iss(line);
				iss >> size;
			} else {
				istringstream iss(line);
				iss >> name >> size;
			}
			names[name] = i;
			sizes.push_back(size);
		}

		vector<ull> values;
		for (int i = 0; i < v; ++i) {
			ull value = 0;
			for (int j = 0; j < sizes[i]; ++j) {
				for (int k = 0; k < b; ++k) {
					char c;
					cin >> c;
					value <<= 1;
					value |= (c == '1' ? 1 : 0);
				}
			}
			values.push_back(value);
		}


		int q;
		cin >> q;
		getline(cin, dummy);

		for (int i = 0; i < q; ++i) {
			string name;
			getline(cin, name);

			cout << name << "=";
			if (names.count(name)) {
				cout << values[names[name]];
			}
			cout << endl;
		}
	}
}

Problem E: Extreme Primitive Society

個体がwとhというプロパティを持っている。(w1, h1)と(w2, h2)という個体が交配すると、(w1, h1)、(w1, h2)、(w2, h1)、(w2, h2)という個体が生まれる。しかも各値は±1することができる。雌雄同体なので誰とでも交配できる。1ターンで全ての個体のペアが交配する。正方形(w=h)の個体が現れるまでに必要な最低ターン数を求めよ。

  • 全部シミュレーションしても間に合うと思うけどかったるいなぁ
  • wとhの初期値の中で一番近いやつがどんどん近づいていくような貪欲でいいんじゃね?多分。
  • 書けた。自信ないけどWA食らったら全部シミュレーションすればいいだけのこと。
  • submit Accepted ・・・え?
int main()
{
	int testCase = 1;
	for (int n; cin >> n; ) {
		vector<int> xs;
		vector<int> ys;
		int answer = INT_MAX;
		for (int i = 0; i < n; ++i) {
			int x, y;
			cin >> x >> y;
			xs.push_back(x);
			ys.push_back(y);
			if (x == y) {
				answer = 0;
			}
		}
		for (vector<int>::iterator x = xs.begin(); x != xs.end(); ++x) {
			for (vector<int>::iterator y = ys.begin(); y != ys.end(); ++y) {
				answer = min(answer, max((abs(*x - *y) + 1) / 2, 1));
			}
		}

		printf("Case %d : %d\n", testCase++, answer);
	}
}

Problem F: Few Teams will Solve This

あるグラフをBFS/DFSした時に通ったノードの番号が与えられる。これらを満たすようなグラフがいくつあるか求めよ。

  • 無理

Problem G: Giving Candies

与えられた文字列の中から文字の位置が重複しないように同じ文字列を2個取り出す。ただし指定された文字は使ってはならない。取り出せる文字列の中で一番長い文字列の長さを求めよ。

  • でたあっー・・・文字列アルゴリズムゲー
  • 苦手なんだよなぁ・・・っていくつ苦手あるんだ自分
  • さて、同じ文字列を取り出すんだからきっとSuffixほげほげ系に違いない!
  • とりあえず自分が知っているTrieとか使ってみる
  • Trieの更新の時に長さと文字列が始まったいちを覚えさせて、あとから集計してみる
  • TLE
  • 定数高速化
  • TLE
  • TLE
  • 集計のタイミングを早めてみた
  • TLE
  • TLE
  • TLE
  • どうしろと・・・。
  • これは純粋なO(N^2)アルゴリズムを考えるしか無いなぁ
  • なんか尺取メソッド的なの使えないかなぁ
  • ピ∀゚コーン 2つの文字列の相対位置で回せば左からなめるだけじゃん
  • WA
  • WA
  • WA
  • どうしろと・・・。
  • stripって輪って意味だよなぁ・・・?
  • 輪・・・だっけ?
  • ひも・・・じゃね?
  • ひもかぁ・・・。
  • 文字列はループしないのかぁ。そうかぁ。
  • Accepted orz
  • 14ペナルティって・・・orz
int main()
{
	int N;
	scanf("%d", &N);
	char line[1024];
	gets(line);

	for (int testCase = 1; testCase <= N; ++testCase) {
		const int lineLength = strlen(gets(line));
		char ng[1024];
		const int ngLength = strlen(gets(ng));

		bool ngTable[0x100];
		memset(ngTable, 0, sizeof(ngTable));
		for (int i = 0; i < ngLength; ++i) {
			ngTable[ng[i]] = true;
		}

		int answer = 0;
		for (int delta = 1; delta < lineLength; ++delta) {
			int length = 0;
			for (int index = 0; index + delta < lineLength; ++index) {
				const char a = line[index % lineLength];
				const char b = line[(index + delta) % lineLength];
				if (ngTable[a] || ngTable[b] || a != b) {
					length = 0;
				} else {
					++length;
					if (length > delta) {
						length = delta;
					}
					if (answer < length) {
						answer = length;
					}
				}
			}
		}

		printf("Case #%d: %d\n", testCase, answer);
	}
}

Problem H: How Dark can it be?

円状の光源から非凸多角形に光を当て、その向こう側の壁に影を作る。濃い影と薄い影の面積を求めよ。

  • 無理ゲー

Problem I: Ignore the Blocks

RxCのマスに1x2のブロックを敷き詰める方法が何通りあるか求めよ。ただし所々ブロックを置けないマス目がある。

  • はいはいDPDP
  • と思ったらR<=4でC<=100000000??? DP無理じゃん
  • この数だったら行列のN乗の出番だよなぁ
  • でも途中の障害物どうしよう
  • 障害物が無いところは行列のN乗で、障害物のあるところはDPに切り替えればよいのか!
  • 実装難しそう・・・orz
  • 無理でした

結果

UserABCDEFGHISolvedTotal time
28nodchip00:24:15 (0)00:30:50 (0)01:20:29 (1)03:07:38 (3)02:01:24 (0)00:00:00 (0)04:53:11 (14)00:00:00 (0)00:00:00 (0)618:17:47

まぁまぁ良かったのではないかと思います。

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