Hatena::Grouptopcoder

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

 | 

2013-01-14

Codeforces Round #160 (Div. 1) 11:08 Codeforces Round #160 (Div. 1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Round #160 (Div. 1) - nodchipのTopCoder日記 Codeforces Round #160 (Div. 1) - nodchipのTopCoder日記 のブックマークコメント

昨夜のTopCoderに引き続き大惨敗回でした。

A. Maxim and Discounts

  • 貪欲?DP
  • DPしたらO(nm)TLEするよなぁ
  • 解き方分からない・・・
  • 試しにDP書いてみる
  • Time limit exceeded on pretest 13
  • もしかして一番小さいqしか使わない貪欲・・・?
  • 反例あるかな・・・?
  • ・・・
  • なさそう・・・?
  • 書いてみる
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);

	int m;
	cin >> m;
	vector<int> qs;
	REP(i, m) {
		int q;
		cin >> q;
		qs.push_back(q);
	}
	sort(ALL(qs));

	int n;
	cin >> n;
	vector<ll> as;
	REP(i, n) {
		int a;
		cin >> a;
		as.push_back(a);
	}
	sort(ALL(as), greater<ll>());

	vector<ll> sum;
	sum.push_back(0);
	partial_sum(ALL(as), back_inserter(sum));

	ll answer = sum.back();
	int index = 0;
	ll price = 0;
	while (index + qs[0] < n) {
		price += sum[index + qs[0]] - sum[index];
		index += qs[0] + 2;
		MIN_UPDATE(index, n);
		MIN_UPDATE(answer, price + sum[n] - sum[index]);
	}
	cout << answer << endl;
}

B. Maxim and Restaurant

  • 見た感じDP
  • でもやり方が全くわからない
  • orz
  • Opened
  • dreamoon4さんのコードを参考に書いてみる
  • この人が来たら入れなくなるという人でループ
  • それ以外の人で[何人目][既に入ったゲストの数][サイズの総和]というdp表を作る
  • 最後に入れなかった人が本当に入れないパターンでフィルタして、パターン数*既に入ったゲストの数を足していく
  • Wrong answer on test 22
  • パターン数の計算間違えた
  • Wrong answer on test 29
  • 全員入れる場合の処理間違えた
  • 以下はPracticeで通したコードです
double fact[64];

double go(vector<int>& as, int p, int last) {
	// [何番目][何人][サイズの和]
	static double dp[64][64][64];
	CLEAR(dp);
	dp[0][0][0] = 1;

	REP(index, as.size()) REP(guests, as.size()) REP(sumOfSize, p + 1) {
		dp[index + 1][guests][sumOfSize] += dp[index][guests][sumOfSize];
		if (sumOfSize + as[index] <= p) {
			dp[index + 1][guests + 1][sumOfSize + as[index]] += dp[index][guests][sumOfSize];
		}
	}

	double answer = 0;
	REP (guests, as.size() + 1) REP(sumOfSize, p + 1) {
		if (dp[as.size()][guests][sumOfSize] && sumOfSize + last > p) {
			double diff = guests * dp[as.size()][guests][sumOfSize] * fact[guests] * fact[as.size() - guests];
			answer += diff;
			//printf("last=%d guests=%d sumOfSize=%d dp=%d diff=%e\n", last, guests, sumOfSize, dp[as.size()][guests][sumOfSize], diff);
		}
	}
	return answer;
}

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

	fact[0] = 1;
	for (int i = 1; i < 64; ++i) {
		fact[i] = fact[i - 1] * i;
	}

	int n;
	cin >> n;
	vector<int> as;
	REP(i, n) {
		int a;
		cin >> a;
		as.push_back(a);
	}

	int p;
	cin >> p;

	if (accumulate(ALL(as), 0) <= p) {
		cout << n << endl;
		return 0;
	}

	double answer = 0;
	REP(i, n) {
		vector<int> others = as;
		others.erase(others.begin() + i);
		answer += go(others, p, as[i]);
	}

	printf("%.20lf\n", answer / fact[n]);
}

C. Maxim and Matrix

  • 小さいサイズで実験してみる
  • どうやらm+1行目の1の数は(1 << (countPop(m) - 1))になるらしい (<-間違い)
  • これは一番上のビットから探索して、途中nCm使って枝刈りで良いのではないか?
  • 書いてみる
  • Wrong answer on pretest 9
  • 何が間違っているのかわからないorz
  • 実はm+1行目の1の数は(1 << (countPop(m+1) - 1))だった
  • 一行修正
  • 通った
  • 以下はPracticeで通したソースコードです
ll C[64][64];

// 何ビット目以降を見ているか
// 残りビット数
// 現在の値
ll dfs(int bit, int remainOne, ll currentValue, ll n) {
	assert(remainOne);
	if (bit + 1 < remainOne) {
		return 0;
	}

	ll answer = 0;
	if (currentValue + (((1LL << remainOne) - 1) << (bit + 1 - remainOne)) <= n) {
		answer += C[bit + 1][remainOne];
	} else {
		if (currentValue + (1LL << bit) <= n) {
			answer += dfs(bit - 1, remainOne - 1, currentValue + (1LL << bit), n);
		}
		answer += dfs(bit - 1, remainOne, currentValue, n);
	}
	return answer;
}

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

	C[0][0] = 1;
	for (int i = 1; i < 64; ++i) REP(j, 64) {
		if (j) {
			C[i][j] += C[i - 1][j - 1];
		}	
		C[i][j] += C[i - 1][j];
	}

	ll n, t;
	cin >> n >> t;

	int popCount = 0;
	int logT = 0;
	REP(i, 44) {
		if ((1LL << i) & t) {
			logT = i;
			++popCount;
		}
	}

	if (popCount != 1) {
		cout << 0 << endl;
		return 0;
	}

	cout << dfs(44, logT + 1, 0, n + 1) - dfs(44, logT + 1, 0, 1) << endl;
}

System Test

oxx-- 250 418位 1922->1838

確率DPと問題読み間違いが同時に来て残念な結果になってしまいましたorz

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