Hatena::Grouptopcoder

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

 | 

2010-07-10

Codeforces Beta Round #23 03:23 Codeforces Beta Round #23 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #23 - nodchipのTopCoder日記 Codeforces Beta Round #23 - nodchipのTopCoder日記 のブックマークコメント

A. You're Given a String...

  • ループ回すだけ・・・?
  • だよね
  • O(N^3)

結果: Accepted

bool check(const string& s, const string& sub) {
	const size_t index = s.find(sub);
	if (index == string::npos) {
		return false;
	}
	if (s.find(sub, index + 1) == string::npos) {
		return false;
	}
	return true;
}

int main() {
	string s;
	getline(cin, s);

	for (int length = s.size(); length >= 0; --length) {
		for (int index = 0; index <= s.size() - length; ++index) {
			const string sub = s.substr(index, length);
			if (check(s, sub)) {
				cout << length << endl;
				return 0;
			}
		}
	}

	cout << 0 << endl;
}

B. Party

  • 状況が全然つかめない
  • とりあえず図を書いてみる
  • たとえば ○-○-○ とつながっていたときはどうだろう
  • 友達0人の人はいなくて、友達1人の人が2人帰って、残った人が友達0人になって・・・
  • 一人残った
  • 多分こういう事らしい
  • さて、最適な組み合わせを考えないと・・・
  • こういう時は特徴的なグラフを考えると相場が決まっている(本当か?)
  • 完全グラフとか、完全グラフから1本抜くとか
  • 完全グラフから1本抜けばいいんじゃね?
  • そんな気がする
  • で、N=1のときは誰も残らないあから、max(0,N-2)とか
  • ・・・本当か?
  • とりあえず書くしか無い

結果: Accepted

int main() {
	int T;
	cin >> T;
	REP(t, T) {
		int N;
		cin >> N;
		cout << max(0, N - 2) << endl;
	}
}

C. Oranges and Apples

  • どうやるんだろう・・・
  • 全然検討がつかない・・・
  • ソートとかするのかなぁ・・・
  • orz

D. Tetragon

  • これ解けるかも
  • 最初の点を座標-10~20の範囲で0.5刻みで回して全探索すればいいんじゃね?
  • 書いてみた
  • TLE
  • 手元で回してみる
  • 全然間に合ってない
  • 計算量でかくね・・・?
  • orz

E. Tree

  • O(N^3)まで許されるらしい
  • メモつき探索かなにかかなぁ・・・
  • でも全然思いつかないorz

結果

#Who=PenaltyABCDE
51nodchip222+00:05+00:17 -2

2010 TCO Algorithm Online Round 3 03:13 2010 TCO Algorithm Online Round 3 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 2010 TCO Algorithm Online Round 3 - nodchipのTopCoder日記 2010 TCO Algorithm Online Round 3 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 SieveOfEratosthenes

  • なんか数論っぽい
  • 嫌な予感がする・・・
  • とりあえず全部試すとTLE
  • どうしよう・・・
  • なんかgreedyに解かないといけないんだろうなぁ
  • 手で書き出してみようか
  • 外側のループの変数は高々maxNum^0.5しか回らない
  • どちらの値も素数のハズ・・・(<-間違い)
  • そのあたりの値iを使ってもうひとつの値jを二分探索できないか?
  • 出来そう
  • 書けた
  • submit!

結果: Challenge Succeeded

  • 8の解きだけは2*4で素数*素数にならないらしい・・・
    • これは気付けないorz

以下はPracticeで通ったソースコードです

#define MAX (256*1024)

class SieveOfEratosthenes {
public:
	int lastScratch(int maxNum) {
		if (maxNum == 8) {
			return 8;
		}

		// エラトステネスの篩
		static bool flag[MAX];
		memset(flag, -1, sizeof(flag));
		flag[0] = flag[1] = false;
		for (int i = 2; i * i < MAX; ++i){
			if (!flag[i]){
				continue;
			}
			for (int j = i * i; j < MAX; j += i){
				flag[j] = false;
			}
		}
		vector<ll> primes;
		for (int i = 2; i < MAX; ++i){
			if (flag[i]){
				primes.push_back(i);
			}
		}

		ll start = sqrt((double)maxNum) + 1;
		ll answer = -1;
		for (ll left = start; left >= 1; --left) {
			if (!flag[left]) {
				continue;
			}

			vector<ll>::iterator it = upper_bound(ALL(primes), maxNum / left);
			if (it != primes.begin()) {
				--it;
			}
			const ll right = *it;
			if (left > right || right * left > maxNum) {
				continue;
			}

			if (left * right > answer) {
				answer = left * right;
				break;
			}
		}

		int result = (int)answer;
		return result;
	}
}

Medium 500 TheChroniclesOfAmber

  • グラフすなぁ
  • これループ回していけるんじゃね?
  • 一番近いところにワープすればいい気がしてきた
  • ・・・
  • 全員ワープすることはできないっぽい
  • ひとりだけワープさせなきゃいいんじゃね?
  • 強連結成分が2つあった時の処理が分からないorz
  • ううむ・・・
  • 適当に貪欲っぽく書いてみよう
  • ・・・
  • あれ、答えが合わないorz

結果: Opened

  • 結局、ひとりだけワープさせないで貪欲+全員テレポート無しの併用で良いらしい・・・orz
    • 証明が微妙に出来ていないorz

以下はPracticeを通したソースコードです。

typedef complex<double> P;

class TheChroniclesOfAmber {
public:
	double minimumTime(vector <int> princeX, vector <int> princeY, vector <int> destinationX, vector <int> destinationY) {
		const int N = princeX.size();
		vector<P> princes;
		vector<P> destinations;
		REP(i, N) {
			princes.push_back(P(princeX[i], princeY[i]));
			destinations.push_back(P(destinationX[i], destinationY[i]));
		}

		double result = -1;
		REP(i, N) {
			result = max(result, abs(princes[i] - destinations[i]));
		}

		REP(r, N) {
			double maxDistance = 0;
			REP(i, N) {
				double minDistance = 1e10;
				REP(j, N) {
					if (r == j) {
						continue;
					}
					minDistance = min(minDistance, abs(princes[j] - destinations[i]));
				}
				maxDistance = max(maxDistance, minDistance);
			}
			result = min(result, maxDistance);
		}

		return result;
	}
}

Hard 1000 Passwords

  • DPですね、分かります。
  • (即座に右上のxボタンを押しました)

Challenge Phase

  • 現在のスコアから行くと1回落とさないと上に上がれないっぽいなぁ
  • !!!
  • なんか絨毯爆撃されている!?
  • 自分のやつ落ちた!?
  • ・・・
  • もうだめだ

System Test

x x x 0pts negative scoreだけは避けられました・・・。いずれにせよRound 3敗退です。

ゲスト



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