Hatena::Grouptopcoder

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

 | 

2010-04-16

SingleRoundMatch467@TopCoder 21:59 SingleRoundMatch467@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch467@TopCoder - nodchipのTopCoder日記 SingleRoundMatch467@TopCoder - nodchipのTopCoder日記 のブックマークコメント

今回の目標はGoogle先生を有効に使うことでした

Easy 250 LateProfessor

  • 時間が10000000までしか内から全部試せばいいんじゃね?
  • 書き始める
  • 答えが合わない
  • 遅刻の意味を取り違えていたらしい
  • 直してみた
  • 最後のexampleでNanが出た
  • なん・・・だと・・・
  • beginとlastが同じ場合は別処理が必要らしい
  • 条件がかなり不安
  • とくにwaitが終わった瞬間に教授が来た場合
  • inclusiveと書いてあるのでこれで良いはず・・・
  • submit

結果 : Passed System Test

class LateProfessor {
public:
	double getProbability(int waitTime, int walkTime, int lateTime, int bestArrival, int worstArrival) {
		if (bestArrival == worstArrival) {
			const int tt = bestArrival % (waitTime + walkTime);
			if (waitTime < tt && tt <= (waitTime + walkTime) - lateTime) {
				return 1.0;
			} else {
				return 0.0;
			}
		}

		int sum = 0;
		for (int t = bestArrival; t < worstArrival; ++t) {
			const int tt = t % (waitTime + walkTime);
			if (waitTime <= tt && tt < (waitTime + walkTime) - lateTime) {
				++sum;
			}
		}


		double result = sum / (double)(worstArrival - bestArrival);
		return result;
	}
}

Middle 500 SuperSum

  • わけが・・・分からない・・・
  • 取り敢えず落ち着いて考えよう
  • きっと何らかの変形ができるはず
  • 紙に表を書いてみる
  • これS(k,n)=\sum_{i=1}^{n}S(k-1,i)=S(k-1,n)+\sum_{i=1}^{n-1}S(k-1,i)=S(k-1,n)+S(k,n-1)じゃね・・・?
  • この形どこかで見たことある・・・
  • パスカルの三角形?
  • 一番上に1,1,1,...,1を追加すると正しくパスカルの三角形!
  • 変数を調整してみる
  • {}_{n+k}C_{k+1}
  • mod面倒だなぁ・・・逆元求める方法があるのは知っているけど・・・
  • BigIntegerでやっちゃえ!
  • submit

結果 : Passed System Test

import java.math.BigInteger;

public class SuperSum {
	public int calculate(int k, int n) {
		BigInteger nk = BigInteger.valueOf(k + n);
		BigInteger answer = BigInteger.ONE;
		for (int i = 0; i <= k; ++i) {
			answer = answer.multiply(nk.subtract(BigInteger.valueOf(i)));
			answer = answer.divide(BigInteger.valueOf(i + 1));
		}
		answer = answer.mod(BigInteger.valueOf(1000000007));
		return answer.intValue();
	}
}

Hard 1000 NextHomogeneousStrings

  • 考えていません

Challenge Phase

  • 250でbegin=lastでwaitが終わった瞬間に教授が来るやつを狙ってみよう
  • この人落ちそう
  • だけどコードがぐちゃぐちゃで何やっているか分からないのでパス
  • この人も落ちそう
  • だけどやっぱりぐちゃぐちゃで読めない
  • この人は落とせそう
  • と思ったら先に落とされたorz

System Test

o o x 436.86 久々に良い成績が取れました

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

Problem A Power Consumption Calculation

  • 愚直にシミュレーションするだけ
  • バグが取れなくて時間をくってしまった
int main() {
	int n, P1, P2, P3, T1, T2;
	cin >> n >> P1 >> P2 >> P3 >> T1 >> T2;
	int use[2048];
	memset(use, 0, sizeof(use));
	int begin = INT_MAX;
	int end = 0;
	for (int i = 0; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		fill(use + l, use + r + 1, 1);
		begin = min(begin, l);
		end = max(end, r);
	}

	int sum = 0;
	int sleep = 0;
	for (int t = begin; t < end; ++t) {
		if (use[t]) {
			sleep = 0;
		}
		if (sleep >= T1 + T2) {
			sum += P3;
		} else if (sleep >= T1) {
			sum += P2;
		} else {
			sum += P1;
		}

		//cout << t << " " << sum << endl;

		++sleep;
	}
	cout << sum << endl;
}

Problem B

  • 全部調べても間に合う
  • 調べる順番を調整すると場合分けをせずにすむ
static int seats[128][128];

int main() {
	memset(seats, 0, sizeof(seats));

	int N, K;
	cin >> N >> K;
	for (int n = 0; n < N; ++n) {
		int M;
		cin >> M;

		int bestScore = INT_MAX;
		int bestX = -1;
		int bestY = -1;
		for (int x = 1; x <= K; ++x) {
			for (int y = 1; y <= K - M + 1; ++y) {
				if (find(&seats[x][y], &seats[x][y + M], 1) != &seats[x][y + M]) {
					continue;
				}

				int score = 0;
				for (int m = 0; m < M; ++m) {
					score += abs(x - (K + 1) / 2) + abs(y + m - (K + 1) / 2);
				}

				if (bestScore > score) {
					bestScore = score;
					bestX = x;
					bestY = y;
				}
			}
		}

		if (bestX == -1) {
			cout << -1 << endl;
		} else {
			cout << bestX << " " << bestY << " " << bestY + M - 1 << endl;

			for (int m = 0; m < M; ++m) {
				seats[bestX][bestY + m] = 1;
			}
		}
	}
}

Problem C Digital Root

  • 問題文が読みにくい
  • ・・・と赤コーダーのLinesPower氏よりチャットで愚痴を言われた
  • 自分もそう思う
  • df(df(a)*df(b))==df(c) && a*b!=cとなる1<=a,b,c<=Nのabcの組が何通りあるか答えれば良い
  • ・・・はずなんだけど何で答えが合わないのorz

Problem D LCIS

  • ミスジャッジにより問題文が差し替えられた
  • Longest Common SequenceとLongest Increasing Scequenceを同時にやると言う問題
  • 頭の中ではO(N^3)で行けそうな気がしているのだけれど、実際に出来るかどうかは要検証

Problem E Greedy Change

  • 実は有名問題だったらしい
  • LinesPower氏に元論文を教えて頂いた
  • 後ほど読んでみる予定

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

Problem A Train and Peter

  • やるだけ
int main() {
	string colors, a, b;
	cin >> colors >> a >> b;
	bool forward = false;
	size_t index;
	if ((index = colors.find(a)) != string::npos) {
		forward = colors.find(b, index + a.size()) != string::npos;
	}

	reverse(colors.begin(), colors.end());
	bool backward = false;
	if ((index = colors.find(a)) != string::npos) {
		backward = colors.find(b, index + a.size()) != string::npos;
	}

	if (forward && backward) {
		cout << "both" << endl;
	} else if (forward) {
		cout << "forward" << endl;
	} else if (backward) {
		cout << "backward" << endl;
	} else {
		cout << "fantasy" << endl;
	}
}

Problem B Obsession with Robots

  • 一度訪れたマス、またはその上下左右のマスに来た場合は直接そのマスに行くルートがあるので最適ではない
  • 訪れたマスをメモするだけ
static const int DX[] = {1, -1, 0, 0};
static const int DY[] = {0, 0, 1, -1};

bool check(const string& in) {
	int dx[128];
	int dy[128];
	memset(dx, 0, sizeof(dx));
	memset(dy, 0, sizeof(dy));
	dx['R'] = 1;
	dx['L'] = -1;
	dy['U'] = 1;
	dy['D'] = -1;

	set<pair<int, int> > memo;
	memo.insert(make_pair(0, 0));

	int x = 0;
	int y = 0;
	for (string::const_iterator it = in.begin(); it != in.end(); ++it) {
		const char c = *it;
		const int nextX = x + dx[c];
		const int nextY = y + dy[c];
		
		if (memo.count(make_pair(nextX, nextY))) {
			return false;
		}

		int counter = 0;
		for (int direction = 0; direction < 4; ++direction) {
			if (memo.count(make_pair(nextX + DX[direction], nextY + DY[direction]))) {
				++counter;
			}
		}
		
		if (counter >= 2) {
			return false;
		}

		x = nextX;
		y = nextY;
		memo.insert(make_pair(x, y));
	}

	return true;
}

int main() {
	string in;
	cin >> in;

	if (check(in)) {
		cout << "OK" << endl;
	} else {
		cout << "BUG" << endl;
	}
}

Problem C Looking for Order

  • 巡回セールスマンで解けるだろうと誤解しO(2^N N^2)突っ込んでTLE
  • 幅優先っぽく書き換えるもPE
  • PEってどういうこと・・・

Problem D Two Friends

  • 考えていません

Problem E Beads

  • 考えていません

ゲスト



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