Hatena::Grouptopcoder

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

 | 

2010-07-10

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
 |