Hatena::Grouptopcoder

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

 | 

2010-01-19

SingleRoundMatch459@TopCoder 03:16 SingleRoundMatch459@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch459@TopCoder - nodchipのTopCoder日記 SingleRoundMatch459@TopCoder - nodchipのTopCoder日記 のブックマークコメント

SingleRoundMatch459@TopCoderの参加記録です。

Easy 250 Inequalities

50個までの不等式が与えられる。満たすことが出来る不等式の数が最大になるようにXを選んだ時の、不等式の数を求めよ。

  • なんか最近の250激しすぎません・・・?
  • 実装系だよなぁ。重そうだなぁ。
  • ・・・これXで回して不等式愚直に調べるだけじゃね?

結果 : Passed System Test

class Inequalities {
public:
	int maximumSubset(vector <string> inequalities) {
		int result = 0;
		for (int x = -1; x <= 2001; ++x) {
			int counter = 0;
			for (vector<string>::iterator it = inequalities.begin(); it != inequalities.end(); ++it) {
				istringstream iss(*it);
				string xx, op;
				int C;
				iss >> xx >> op >> C;
				C *= 2;
				if (op == "<") {
					counter += (x < C);
				} else if (op == "<=") {
					counter += (x <= C);
				} else if (op == "=") {
					counter += (x == C);
				} else if (op == ">") {
					counter += (x > C);
				} else if (op == ">=") {
					counter += (x >= C);
				}
			}
			result = max(result, counter);
		}
		return result;
	}
}

Middle 500 NumberPyramids

一番下にbaseLength個の数字を置き、一段上がるごとに右下と左下の数字を足していく。このようにしてできた物のうち、頂点の数字がtopの物が何通りあるか求めよ。

  • 来ましたDP
  • 一番左の列に着目してDPっぽく解けば良いのかなぁ?
  • 試しに書いてみたけどぜんぜん答え違うorz
  • そもそも計算量がO(N^2)になってて間に合わない
  • 一番下に着目してみる?
  • 一番下の数ってなんかいたされてtopに来るんだろう?
  • "1 2 1", "1 4 6 4 1", "1 5 10 10 5 1"
  • これnCiじゃん!
  • 要はn = baseLength - 1として\sum^{n}_{i=0} A_{i} * _{n}C_{i} = top (A_{i} >= 1)を満たすAiが何通りあるか求めれば良いのか。
  • で・・・どうすんだ?
  • 左からDPっぽくやってみる?
  • O(N^2)だなぁorz
  • なんかお釣りの払い方DPっぽいんだよなぁ
  • A_{i} >= 1がA_{i} >= 0なら、まんまお釣りの払い方DPなんだけどなぁ・・・
  • ・・・!!!
  • topからΣAi引いとけばA_{i} >= 0と等価だ!
  • 残り1分切ってる!
  • 間に合うか!?

結果 : Passed System Test

static const int MOD = 1000000009;

int add(int a, int b)
{
	return (a + b) % MOD;
}

int mul(int a, int b)
{
	return (a * b) % MOD;
}

class NumberPyramids {
public:
	int count(int baseLength, int top) {
		if (baseLength >= 21) {
			return 0;
		}
		if ((1 << (baseLength - 1)) > top) {
			return 0;
		}

		int tri[32][32];
		memset(tri, 0, sizeof(tri));
		tri[1][1] = 1;
		for (int i = 2; i < 32; ++i) {
			for (int j = 1; j <= i; ++j) {
				tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
			}
		}

		int sum = 0;
		for (int coin = 1; coin <= baseLength; ++coin) {
			sum += tri[baseLength][coin];
		}
		if (top < sum) {
			return 0;
		}

		vector<int> dp(1024 * 1024);
		dp[0] = 1;
		for (int coin = 1; coin <= baseLength; ++coin) {
			for (int value = 0; value < 1024 * 1024; ++value) {
				const int c = tri[baseLength][coin];
				if (value - c >= 0) {
					dp[value] = add(dp[value], dp[value - c]);
				}
			}
		}

		return dp[top - sum];
	}
}

Hard 1000 TheContest

  • なんか実装系に見える
  • サンプルから規則性を導き出せないか・・・
  • 無理でしたorz

Challenge Phase

  • 500でO(N^2)の人を1撃墜
  • 250で境界条件の"X < 0"、"X > 1000"で落とせる人を探すが、1失敗

System Test

o o x +25 1965 -> 2018

残り数秒でのsubmitは懲り懲りです。

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