Hatena::Grouptopcoder

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

 | 

2011-03-18

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

A. Irrational problem

  • かくだけ!
    • (実は問題文を勘違いしていて、permutationを書けるのを忘れていた)
  • Accepted
    • (さらにpermutationは掛けなくても通ることが分かった)
int main() {
	std::ios::sync_with_stdio(false);
	
	int p1, p2, p3, p4, a, b;
	cin >> p1 >> p2 >> p3 >> p4 >> a >> b;
	int answer = 0;
	for (int i = a; i <= b; ++i) {
		if (i % p1 % p2 % p3 % p4 == i) {
			++answer;
		}
	}
	cout << answer << endl;
}

B. Energy exchange

  • 大きなやつを小さなやつに振り分けていけば良い気がする
  • 大きなやつと小さなやつの閾値を二部探索すれば良さそう
    • Accepted
int main() {
	std::ios::sync_with_stdio(false);
	
	int N, K;
	cin >> N >> K;
	vector<double> a;
	REP(n, N) {
		double value;
		cin >> value;
		a.push_back(value);
	}

	double l = 0.0;
	double r = 1e10;
	REP(loop, 200) {
		const double m = (l + r) * 0.5;

		double rest = 0.0;
		double need = 0.0;
		REP(n, N) {
			if (m > a[n]) {
				need += m - a[n];
			} else {
				rest += a[n] - m;
			}
		}

		if (rest - rest * K * 0.01 < need) {
			r = m;
		} else {
			l = m;
		}
	}

	printf("%.20f\n", l);
}

C. Synchrophasotron

  • DP
  • とりあえずなんちゃってDP書き始めた
  • ・・・
  • 書いている途中で解けないことが判明
  • 入力サイズがやけに小さいので全探索っぽい
  • 探索書き始めた
  • 書けた
  • 最大ケースを入れて見る
  • ・・・
  • 止まらないorz
    • けどとりあえず保険で投げてしまえ
  • 高速化してみる
  • 枝刈りを入れてみた
  • 手元で一瞬で終わるようになった
  • submit
  • 問題文の最後の1文を勘違いしていて、余計な処理を入れていた
  • 以下はPracticeで通ったコードです
vector<vector<int> > input;
int in[8];
int out[8];
int minFlow = INT_MAX;
int maxCost = INT_MIN;
int N;

void dfs(int index, int cost) {
	if (index == input.size()) {
		// チェック
		for (int n = 2; n < N; ++n) {
			if (in[n] != out[n]) {
				return;
			}
		}

		if (minFlow > in[N] || (minFlow == in[N] && maxCost < cost)) {
			minFlow = in[N];
			maxCost = cost;
		}

		return;
	}

	const int s = input[index][0];
	const int f = input[index][1];
	const int l = input[index][2];
	const int h = input[index][3];
	const int a = input[index][4];

	const int backupIn = in[f];
	const int backupOut = out[s];

	for (int flow = l; flow <= h; ++flow) {
		in[f] = backupIn + flow;
		out[s] = backupOut + flow;
		const int nextCost = cost + (flow == 0 ? 0 : (a + flow * flow));

		// 枝刈り
		if (in[s] < out[s]) {
			continue;
		}

		if (in[f] > minFlow) {
			continue;
		}

		dfs(index + 1, nextCost);
	}

	in[f] = backupIn;
	out[s] = backupOut;
}

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

	in[1] = INT_MAX / 2;

	cin >> N;
	REP(n, N * (N - 1) / 2) {
		vector<int> row;
		REP(i, 5) {
			int value;
			cin >> value;
			row.push_back(value);
		}

		input.push_back(row);
	}

	sort(ALL(input));

	dfs(0, 0);

	if (minFlow == INT_MAX) {
		cout << "-1 -1" << endl;
	} else {
		cout << minFlow << " " << maxCost << endl;
	}
}

D. Half-decay tree

  • BITっぽい・・・
  • 時間ないのでパス

E. Contact

  • 幾何だけどE問題が解けるわけがないのでパス

Hack

  • Bで変な処理をしている人を見つけた
  • ソート->最大から最小に振り分けるのをループしている
  • 書き写して最大ケースを投げてみたらTLEした
  • Hack -> +1
  • Cでコーナーケースで落ちていそうな人を発見
  • Hack -> -1
  • 自分の問題解釈が間違っていました

System Test

#Who=ABCDE
109nodchip1506+1 / -1496 00:02960 00:10-2

2052->1993 オレンジコーダーになりました。Cの問題文の読み間違いがなければレッドを維持できたかと思うと残念です。

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