Hatena::Grouptopcoder

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

 | 

2015-01-24

Single Round Match 647 Div 1 03:49 Single Round Match 647 Div 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 647 Div 1 - nodchipのTopCoder日記 Single Round Match 647 Div 1 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 BuildingTowersEasy

  • 前と後から1ずつ高さを増やしていくのでは・・・。
  • Passed System Test
class BuildingTowersEasy {
public:
	int maxHeight(int N, vector <int> x, vector <int> t) {
		map<int, int> restrictions;
		REP(i, x.size()) {
			restrictions[x[i]] = t[i];
		}

		vector<int> heights(N + 1);
		for (int n = 2; n <= N; ++n) {
			heights[n] = heights[n - 1] + 1;
			if (restrictions.count(n)) {
				MIN_UPDATE(heights[n], restrictions[n]);
			}
		}

		for (int n = N - 1; n >= 1; --n) {
			MIN_UPDATE(heights[n], heights[n + 1] + 1);
		}

		return *max_element(ALL(heights));
	}
};

Medium 500 CtuRobots

  • とりあえずあるロボットの集合が与えられたときに最も遠くまで行く戦略は・・・
  • capの昇順に並べて一番手前のやつが他のやつ全員に燃料を分け与えるパターン? (←間違い)
  • とりあえずその部分を書いてみる
  • 答えが合わなかった・・・
  • ・・・

hard 1000 ConvenientBlock

  • 最小カットかな?
  • 書いてみる
  • 答えが合わない・・・

Challenge Phase

  • とりあえず250をさらっと見ていく
  • ・・・
  • 読めない・・・
  • 26:00にコードリーディングとか無理ゲー
  • 諦めよう

System Test

oxx 222.61pts 133位 1870→1892 レーティング相当の順位だったようです。

dwangoプログラミングコンテスト dwangoからの『挑戦状』 予選 22:19 dwangoプログラミングコンテスト dwangoからの『挑戦状』 予選 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - dwangoプログラミングコンテスト dwangoからの『挑戦状』 予選 - nodchipのTopCoder日記 dwangoプログラミングコンテスト dwangoからの『挑戦状』 予選 - nodchipのTopCoder日記 のブックマークコメント

A - プレミアム会員

  • やるだけ
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	int n, x;
	cin >> n >> x;
	cout << 540 * x + 525 * (n - x) << endl;
}

B - ニコニコ文字列

  • 部分文字列って飛び飛びになっても良い方だっけ? (←間違い)
  • だとするとdp[2][|S|]だよなぁ・・・
  • 書いてみる
  • 答え合わない
  • 飛び飛びにならない方か・・・
  • なら文字カウントするだけか
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	string S;
	cin >> S;
	ll answer = 0;
	ll n = 0;
	for (char ch : S) {
		if (ch == '2') {
			if (n % 2 == 0) {
				++n;
			}
			else {
				n /= 2;
				answer += n * (n + 1) / 2;
				n = 1;
			}
		}
		else if (ch == '5') {
			if (n % 2 == 1) {
				++n;
			}
			else {
				n /= 2;
				answer += n * (n + 1) / 2;
				n = 0;
			}
		}
		else {
			n /= 2;
			answer += n * (n + 1) / 2;
			n = 0;
		}
	}

	n /= 2;
	answer += n * (n + 1) / 2;
	n = 0;

	cout << answer << endl;
}

C - ゲーマーじゃんけん

  • ああ、これは期待値をメモ探するだけの私が解けない問題ですね。
  • とりあえず取り組んでは見る
  • f(n)をメモ探で書けばいいはずだけど、無限ループする場合があるのでそこをどうにかしないといけなかったはず
  • 確か移行するとか何とかだった気がする。
  • f(n) = \sum^{n}_{i=1} w(i) * (f(i) + 1.0) の形になるはずで、右辺のf(n)を左辺に持ってくればいいのかな?
  • W = \sum^{n-1}_{i=1} w(i) * (f(i) + 1.0) と置いて、f(n) = (W + w(n)) / (1.0 - w(n)) だそうだ
  • っていうかw(i)ってどうやって計算するんだっけ・・・
  • (|グー|+|チョキ|+|パー|)!/|グー|!/|チョキ|!/|パー|! か。高校時代にやった気がする。
  • へぇ
  • とりあえず書いてみる
  • AC
double dp[128];
double fact[128];

double hoge(int a, int b, int c) {
	return fact[a + b + c] / fact[a] / fact[b] / fact[c];
}

double dfs(int N) {
	if (N == 1) {
		return 0.0;
	}

	double& r = dp[N];
	if (r != -1.0) {
		return r;
	}

	double weight[128];
	CLEAR(weight);
	vector<int> hands;
	for (int g = 0; g <= N; ++g) {
		for (int c = 0; c + g <= N; ++c) {
			int p = N - g - c;

			vector<int> hands;
			if (g) {
				hands.push_back(g);
			}
			if (c) {
				hands.push_back(c);
			}
			if (p) {
				hands.push_back(p);
			}
			sort(ALL(hands));

			if (hands.size() == 1) {
				weight[N] += 1.0;
			}
			else {
				int rare = hands[0];
				switch (count(ALL(hands), rare)) {
				case 1:
					weight[hands[0]] += hoge(g, c, p);
					break;
				case 2:
					weight[hands[0]] += hoge(g, c, p);
					break;
				case 3:
					weight[N] += hoge(g, c, p);
					break;
				}
			}
		}
	}

	double sum = accumulate(weight, weight + N + 1, 0.0);
	REP(i, N + 1) {
		weight[i] /= sum;
	}

	double p = 0.0;
	for (int n = 1; n < N; ++n) {
		p += weight[n] * (dfs(n) + 1.0);
	}

	double w = weight[N];
	r = (p + w) / (1.0 - w);

	return r;
}

int main() {
	std::ios::sync_with_stdio(false);

	fill_n(dp, sizeof(dp) / sizeof(dp[0]), -1.0);
	fact[0] = 1.0;
	for (int i = 1; i < 128; ++i) {
		fact[i] = fact[i - 1] * i;
	}

	int N;
	cin >> N;
	double r = dfs(N);
	printf("%.20f\n", r);
}
  • これ系の問題久々に解けた気がする

D - タクシー

  • とりあえず全員時計回りに移動させて、適当に反時計回りに移動させ直せばいいんじゃないかな?
  • 反時計回りに移動させるときに1人ずつ移動させずに複数人まとめて移動させることもできそう。
  • とりあえず書いてみる。
  • RE 15
  • ありゃ・・・
  • バケツソートを配列でやったところで死んでる。
  • これをmapで書き直せば・・・
  • ・・・
  • サンプル通らなくなった
  • 時間切れorz
int main() {
	std::ios::sync_with_stdio(false);
 
	int N, L;
	cin >> N >> L;
	static ll a[128 * 1024];
	static ll b[128 * 1024];
	static ll c[128 * 1024];
	CLEAR(a);
	CLEAR(b);
	CLEAR(c);
	REP(n, N) {
		cin >> a[n] >> b[n] >> c[n];
		ll sub = MIN(b[n], c[n]);
		b[n] -= sub;
		c[n] -= sub;
	}
	a[N] = L;
 
	// index番目の都市から時計回りに何人移動するか?
	static ll initialMoving[128 * 1024];
	CLEAR(initialMoving);
	ll moving = 0;
	REP(n, N * 2) {
		int index = n % N;
 
		int out = MIN(c[index], moving);
		moving -= out;
		c[index] -= out;
 
		moving += b[index];
		b[index] = 0;
 
		initialMoving[index] += moving;
	}
 
	map<ll, ll> initialMovingToCost;
	REP(n, N) {
		initialMovingToCost[initialMoving[n]] += a[n + 1] - a[n];
	}
 
	// [人数] = cost
	static ll bucket[128 * 1024];
	CLEAR(bucket);
	ll current = 0;
	for (const auto& movingToCost : initialMovingToCost) {
		bucket[movingToCost.first] = movingToCost.second;
		current += movingToCost.first * movingToCost.second;
	}
 
	static ll sumToLower[128 * 1024];
	CLEAR(sumToLower);
	sumToLower[0] = bucket[0];
	for (int n = 1; n < 128 * 1024; ++n) {
		sumToLower[n] = sumToLower[n - 1] + bucket[n];
	}
 
	static ll sumToUpper[128 * 1024];
	CLEAR(sumToUpper);
	sumToUpper[128 * 1024 - 1] = bucket[128 * 1024 - 1];
	for (int n = 128 * 1024 - 2; n >= 0; --n) {
		sumToUpper[n] = sumToUpper[n + 1] + bucket[n];
	}
 
	ll best = current;
	for (int n = 0; n < 128 * 1024 - 2; ++n) {
		current -= sumToUpper[n + 1];
		current += sumToLower[n];
		MIN_UPDATE(best, current);
	}
 
	cout << best << endl;
}

E - 電波局

  • よくわからないのでとりあえず10点だけ取っておく
  • WA 10
int main() {
	std::ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	static bool houses[1024][1024];
	CLEAR(houses);

	REP(m, M) {
		int a, b, c;
		cin >> a >> b >> c;
		for (int j = 1; j <= c; ++j) {
			for (int k = 1; k <= j; ++k) {
				houses[a + j - 1][b + k - 1] = true;
			}
		}
	}

	int Q;
	cin >> Q;
	REP(q, Q) {
		int d, e, f;
		cin >> d >> e >> f;
		int counter = 0;
		for (int j = 1; j <= f; ++j) {
			for (int k = 1; k <= j; ++k) {
				if (!houses[d + j - 1][e + k - 1]) {
					++counter;
				}
			}
		}
		cout << counter << endl;
	}
}

結果

順位ユーザ名プレミアム会員ニコニコ文字列ゲーマーじゃんけんタクシー電波局得点 / Total
33nodchip100 01:26100 16:58100 52:4915 99:5110 72:23325 99:51
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20150124
 |