Hatena::Grouptopcoder

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

 | 

2010-04-16

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氏に元論文を教えて頂いた
  • 後ほど読んでみる予定
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100416
 |