Hatena::Grouptopcoder

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

 | 

2010-10-08

Codeforces Beta Round #33 (Codeforces format) 10:25 Codeforces Beta Round #33 (Codeforces format) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #33 (Codeforces format) - nodchipのTopCoder日記 Codeforces Beta Round #33 (Codeforces format) - nodchipのTopCoder日記 のブックマークコメント

A. What is for dinner?

  • やるだけ・・・
    • Accepted
int main() {
	int N, M, K;
	cin >> N >> M >> K;

	static int rows[1024];
	fill_n(rows, 1024, INT_MAX);
	REP(n, N) {
		int r, c;
		cin >> r >> c;
		rows[r] = min(rows[r], c);
	}

	int answer = 0;
	for (int m = 1; m <= M; ++m) {
		answer += rows[m];
	}

	answer = min(answer, K);
	cout << answer << endl;
}

B. String Problem

  • なんか面倒そうな問題だなぁ・・・
  • これ一文字ずつ見るだけじゃね?
  • それぞれの文字について何の文字に変更するかをループで回せば良いっぽい
  • 計算量はO(26N)なので余裕
  • 文字テーブルにワーシャルフロイドをかけるのを忘れずに
    • Accepted
int main() {
	string s, t;
	getline(cin, s);
	getline(cin, t);

	if (s.size() != t.size()) {
		cout << -1 << endl;
		return 0;
	}

	ll g[26][26];
	fill_n((ll*)g, sizeof(g) / sizeof(ll), 0xFFFFFFFFFFFFFFFLL);
	REP(i, 26) {
		g[i][i] = 0;
	}

	int N;
	cin >> N;
	REP(n, N) {
		char src, dst;
		ll cost;
		cin >> src >> dst >> cost;
		src -= 'a';
		dst -= 'a';
		g[src][dst] = min(g[src][dst], cost);
	}

	REP(k, 26) {
		REP(i, 26) {
			REP(j, 26) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}

	ll totalCost = 0;
	string answer;
	REP(i, s.size()) {
		const int src0 = s[i] - 'a';
		const int src1 = t[i] - 'a';
		int bestLetter = -1;
		ll bestCost = 0xFFFFFFFFFFFFFFFLL;
		REP(letter, 26) {
			const ll cost = g[src0][letter] + g[src1][letter];
			if (bestCost > cost) {
				bestCost = cost;
				bestLetter = letter;
			}
		}
		answer += (char)(bestLetter + 'a');
		totalCost += bestCost;

		if (bestLetter == -1) {
			cout << -1 << endl;
			return 0;
		}
	}
	
	cout << totalCost << endl;
	cout << answer << endl;
}

C. Wonderful Randomized Sum

  • DP臭がする・・・
  • とりあえず考えてみる
  • ・・・
  • きっと線形で出来るんだよね?
  • 先頭から見た後で後ろからみるとかかなぁ
  • どこからひっくり返すかが分かればいいから、先頭から見たときはそれまでの総和の最小値を更新するタイミングを保持すれば良さそう
  • あとは後ろから見て行って、prefixの位置をちょっとずつずらしていけばいいっぽい
    • Accepted
int main() {
	int N;
	cin >> N;
	static ll a[128 * 1024];
	ll bestAnswer = 0;
	ll totalSum = 0;
	REP(n, N) {
		cin >> a[n];
		bestAnswer += a[n];
		totalSum += a[n];
	}
	if (bestAnswer < 0) {
		bestAnswer = -bestAnswer;
	}

	vector<int> poss;
	vector<ll> mins;
	poss.push_back(0);
	mins.push_back(0);

	ll sum = 0;
	REP(n, N) {
		sum += a[n];
		if (mins.back() > sum) {
			poss.push_back(n + 1);
			mins.push_back(sum);
		}
	}

	bestAnswer = max(bestAnswer, totalSum - 2 * mins.back());

	sum = 0;
	for (int n = N - 1; n >= 0; --n) {
		while (poss.back() > n) {
			poss.pop_back();
			mins.pop_back();
		}

		sum += a[n];

		ll answer = totalSum - 2 * sum - 2 * mins.back();
		bestAnswer = max(bestAnswer, answer);
	}

	cout << bestAnswer << endl;
}

D. Knights

  • なんかTopCoder SRMでやった問題にそっくり
  • あの時どうやったんだっけ・・・
  • 半直線引いて円と交わる回数求めてマージするとかだっけ・・・
  • でもデータサイズが大きいからTLEしそう・・・
  • ・・・
  • 実はある円に含まれているかどうかだけで行けるんじゃね?
  • 片方にのみ含まれている円の個数を数えれば良いと思う
  • a,bが与えられたときに、予めそれぞれが含まれる円をソートして保持しておけば、マージするだけで行けそう
  • でも時間無いやorz

以下はPracticeで通したプログラムです

int main() {
	int N, M, K;
	cin >> N >> M >> K;
	static ll kx[1024];
	static ll ky[1024];
	REP(n, N) {
		cin >> kx[n] >> ky[n];
	}

	static ll r[1024];
	static ll cx[1024];
	static ll cy[1024];
	REP(m, M) {
		cin >> r[m] >> cx[m] >> cy[m];
	}

	static int in[1024][1024];
	fill_n((int*)in, sizeof(in) / sizeof(int), -1);
	REP(n, N) {
		int index = 0;
		REP(m, M) {
			const ll dx = kx[n] - cx[m];
			const ll dy = ky[n] - cy[m];
			if (r[m] * r[m] > dx * dx + dy * dy) {
				in[n][index++] = m;
			}
		}
	}

	REP(k, K) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;

		int* pa = in[a];
		int* pb = in[b];
		int answer = 0;
		while (!(*pa == -1 && *pb == -1)) {
			if (*pa == -1) {
				++pb;
				++answer;
			} else if (*pb == -1) {
				++pa;
				++answer;
			} else if (*pa == *pb) {
				++pa;
				++pb;
			} else if (*pa < *pb) {
				++pa;
				++answer;
			} else if (*pa > *pb) {
				++pb;
				++answer;
			}
		}
		cout << answer << endl;
	}
}

E. Helper

  • 読んでない

Hack

  • とりあえず見てみる・・・
  • Aとかどこがhack出来るのか分からないのでパス
  • Bを見てみよう・・・
  • ・・・
  • あれ?フロイドワーシャルしてなくね?
  • フロイドワーシャルなしで落ちる例はこんな感じか?
a
b
3
a c 1
c d 1
b d 1
  • Hack!
    • Successful hacking attempt
  • お!きた!
  • まさか他にも居たりして・・・
  • いるいる・・・、ワンサカ要る
    • +700

Final Standings

#Who=ABCDE
76nodchip3190+7486 00:0785400:241150 00:50

良い結果だったと思います。Dが解けていれば上位に食い込めていたのが悔やまれます。

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